Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
Example:
Input: "aab" Output: 1 Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.求最短路径， 可以使用BFS来做 每一层级，找到孩子，加到queue里。
class Solution { public int minCut(String s) { int n = s.length(); int result = 0; Queue<Integer> queue = new LinkedList<>(); queue.add(0); while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { int start = queue.poll(); if (start == n) { return result - 1; } for (int j = start; j < n; j++) { if (isPal(s, start, j)) { queue.add(j + 1); } } } result++; } return result; } private boolean isPal(String s, int start, int end) { while (start <= end) { if (s.charAt(start) != s.charAt(end)) { return false; } start++; end--; } return true; } }问题： 会超时。因为有重复计算。相同的start会重复加入queue。 可以使用一个set，来判断是否加过这个start。
class Solution { public int minCut(String s) { int n = s.length(); int result = 0; Queue<Integer> queue = new LinkedList<>(); // 加入set，来判断是否重复加入了孩子 Set<Integer> set = new HashSet<>(); queue.add(0); while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { int start = queue.poll(); if (start == n) { return result - 1; } for (int j = start; j < n; j++) { if (!set.contains(j + 1) && isPal(s, start, j)) { queue.add(j + 1); set.add(j + 1); } } } result++; } return result; } private boolean isPal(String s, int start, int end) { while (start <= end) { if (s.charAt(start) != s.charAt(end)) { return false; } start++; end--; } return true; } }