首页 > 代码库 > Palindrome Partitioning[leetcode] DFS以及DP的解法
Palindrome Partitioning[leetcode] DFS以及DP的解法
第一种方法是DFS,将所有可能的前缀找到,递归调用partition(剩余字符串)
复杂度为O(2^n)
代码如下:
vector<vector<string>> partition(string s) { vector<vector<string>> res; vector<string> patition; if (s.size() == 0) return res; partition(s, patition, res); return res; } void partition(string s, vector<string>& patition, vector<vector<string>>& res) { for (int i = 1; i < s.size(); i++) { if (isPalindrome(s.substr(0, i))) { patition.push_back(s.substr(0, i)); partition(s.substr(i), patition, res); patition.pop_back(); } } if (isPalindrome(s)) { patition.push_back(s); res.push_back(patition); patition.pop_back(); } } bool isPalindrome(string s) { int l = 0, r = s.size() - 1; while (l <= r) { if (s[l] != s[r]) return false; l++; r--; } return true; }
第二种方法是DP
来自 https://oj.leetcode.com/discuss/9623/my-java-dp-only-solution-without-recursion-o-n-2
res(i)表示s[0...i-1]的所有分解方式
isPalin(i,j)表示s[i...j]是否为回文串
isPalin(i,j) = true if i==j or (s[i] == s[j] and isPalin(i + 1, j - 1)) or (s[i] == s[j] and i + 1 == j)
res(i) = res(j) + s[j...i-1] if isPalin(j, i-1)
vector<vector<string>> partition(string s) { int size = s.size(); vector<vector<vector<string>>> res(size + 1); res[0].push_back(vector<string>(0)); vector<vector<bool>> isPalin(size + 1, vector<bool>(size + 1, false)); for (int i = 0; i < size; i++) { for (int j = 0; j <= i; j++) { if (i == j || s[i] == s[j] && (j + 1 == i || isPalin[j + 1][i - 1])) { isPalin[j][i] = true; for (int p = 0; p < res[j].size(); p++) { vector<string> prefix = res[j][p]; prefix.push_back(s.substr(j, i - j + 1)); res[i + 1].push_back(prefix); } } } } return res[size]; }
Palindrome Partitioning[leetcode] DFS以及DP的解法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。