131. Palindrome Partitioning 发表于 2022-07-12 DP + Backtracking1234567891011121314151617181920212223242526272829303132333435363738class Solution { public List<List<String>> partition(String s) { // 定义 dp[i][j] 表示字符串 s[i, j] 是否为回文字符串,dp[i][j] depends on dp[i + 1][j - 1] boolean[][] dp = new boolean[s.length()][s.length()]; for (int i = s.length() - 1; i >= 0; i--) { for (int j = i; j < s.length(); j++) { if (s.charAt(i) == s.charAt(j)) { if (i + 1 >= j - 1) { dp[i][j] = true; } else { dp[i][j] = dp[i + 1][j - 1]; } } } } List<List<String>> resultList = new ArrayList<>(); Deque<String> wordList = new LinkedList<>(); dfs(resultList, wordList, dp, s, 0); return resultList; } private void dfs(List<List<String>> resultList, Deque<String> wordList, boolean[][] dp, String s, int startIndex) { if (startIndex == s.length()) { resultList.add(new ArrayList<>(wordList)); return; } for (int endIndex = startIndex; endIndex < s.length(); endIndex++) { if (dp[startIndex][endIndex]) { wordList.addLast(s.substring(startIndex, endIndex + 1)); dfs(resultList, wordList, dp, s, endIndex + 1); wordList.removeLast(); } } }} Backtracking123456789101112131415161718192021222324252627282930313233class Solution { public List<List<String>> partition(String s) { List<List<String>> resultList = new ArrayList<>(); List<String> subStrList = new ArrayList<>(); backtrack(resultList, subStrList, s, 0); return resultList; } private void backtrack(List<List<String>> resultList, List<String> subStrList, String s, int startIndex) { if (startIndex == s.length()) { resultList.add(new ArrayList<>(subStrList)); return; } for (int endIndex = startIndex; endIndex < s.length(); endIndex++) { // sub str: [startIndex, endIndex] if (isPalindrome(s, startIndex, endIndex)) { subStrList.add(s.substring(startIndex, endIndex + 1)); backtrack(resultList, subStrList, s, endIndex + 1); subStrList.remove(subStrList.size() - 1); } } } private boolean isPalindrome(String s, int startIndex, int endIndex) { while (startIndex < endIndex) { if (s.charAt(startIndex++) != s.charAt(endIndex--)) { return false; } } return true; }} Reference131. Palindrome Partitioning