首页 > 代码库 > [LeetCode]131 Palindrome Partitioning
[LeetCode]131 Palindrome Partitioning
https://oj.leetcode.com/problems/palindrome-partitioning/
http://blog.csdn.net/linhuanmars/article/details/22777711
public class Solution { public List<List<String>> partition(String s) { List<List<String>> result = new ArrayList<>(); if (s == null || s.isEmpty()) return result; boolean[][] dict = buildDict(s); help(s, dict, 0, new ArrayList<String>(), result); return result; } private void help(String s, boolean[][] dict, int start, List<String> item, List<List<String>> result) { if (start >= s.length()) { result.add(new ArrayList<String>(item)); return; } for (int i = start; i < s.length() ; i ++) { if (!dict[start][i]) continue; item.add(s.substring(start, i + 1)); help(s, dict, i + 1, item, result); item.remove(item.size() - 1); } } // dict[i][j] means substring(i, j + 1) is palin // dict(i, j) = char[i] == char[j] && dict(i + 1, j - 1) // So i starts from s.length to 0 // j starts from i to s.length private boolean[][] buildDict(String s) { int len = s.length(); boolean[][] dict = new boolean[len][len]; for (int i = len - 1 ; i >= 0 ; i --) { for (int j = i ; j < len ; j ++) { if (i == j) dict[i][j] = true; else if(i + 1 == j) dict[i][j] = s.charAt(i) == s.charAt(j); else dict[i][j] = s.charAt(i) == s.charAt(j) && dict[i + 1][j - 1]; } } return dict; } }
[LeetCode]131 Palindrome Partitioning
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。