思路還是采用動態規劃,和WordBreak很像,只不過dict需要事先自己算出,LeetCode的discussion裡有一個方法可以邊動規邊計算dict,本質上沒有區別,兩次循環復雜度為O(n).
public class Solution { public int minCut(String s) { if (s == null || s.length() < 1) { return 0; } int len = s.length(); // pal[i][j] == true, means s.substring(i, j + 1) is palindrome // obsviously, when j - i < 1, pal[i][j] = true boolean pal[][] = getDict(s); // dp[i] is the min cuts of s.substring(i, len) int dp[] = new int[len]; dp[len - 1] = 0; for (int i = len - 2; i >= 0; i--) { dp[i] = len - i - 1; // max cut for (int j = i; j < len; j++) { if (pal[i][j]) { if (j == len - 1) { dp[i] = 0; break; } else if (dp[j + 1] + 1 < dp[i]){ dp[i] = dp[j + 1] + 1; } } } } return dp[0]; } private boolean[][] getDict(String s) { int len = s.length(); boolean[][] pal = new boolean[len][len]; for (int i = len - 1; i >= 0; i--) { for (int j = i; j < len; j++) { if (s.charAt(i) == s.charAt(j) && (j - i < 2 || pal[i + 1][j - 1])) { pal[i][j] = true; } } } return pal; } }