首页 > 搜索 > DFS搜索 > LeetCode-Palindrome Partitioning[DFS]
2014
11-18

LeetCode-Palindrome Partitioning[DFS]

Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",

Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

标签: Backtracking
分析

在每一步都可以判断中间结果是否为合法结果,用回溯法。

一个长度为n的字符串,有$n-1$个地方可以砍断,每个地方可断可不断,因此复杂度为$O(2^{n-1})$

代码1

//LeetCode, Palindrome Partitioning
// 时间复杂度O(2^n),空间复杂度O(n)
class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> result;
        vector<string> path;  // 一个partition方案
        dfs(s, path, result, 0, 1);
        return result;
    }

    // s[0, prev-1]之间已经处理,保证是回文串
    // prev 表示s[prev-1]与s[prev]之间的空隙位置,start同理
    void dfs(string &s, vector<string>& path,
            vector<vector<string>> &result, size_t prev, size_t start) {
        if (start == s.size()) { // 最后一个隔板
            if (isPalindrome(s, prev, start - 1)) { // 必须使用
                path.push_back(s.substr(prev, start - prev));
                result.push_back(path);
                path.pop_back();
            }
            return;
        }
        // 不断开
        dfs(s, path, result, prev, start + 1);
        // 如果[prev, start-1] 是回文,则可以断开,也可以不断开(上一行已经做了)
        if (isPalindrome(s, prev, start - 1)) {
            // 断开
            path.push_back(s.substr(prev, start - prev));
            dfs(s, path, result, start, start + 1);
            path.pop_back();
        }
    }

    bool isPalindrome(const string &s, int start, int end) {
        while (start < end && s[start] == s[end]) {
            ++start;
            --end;
        }
        return start >= end;
    }
};

代码2

//LeetCode, Palindrome Partitioning
// 时间复杂度O(2^n),空间复杂度O(n)
class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> result;
        vector<string> path;  // 一个partition方案
        DFS(s, path, result, 0);
        return result;
    }
    // 搜索必须以s[start]开头的partition方案
    void DFS(string &s, vector<string>& path,
            vector<vector<string>> &result, int start) {
        if (start == s.size()) {
            result.push_back(path);
            return;
        }
        for (int i = start; i < s.size(); i++) {
            if (isPalindrome(s, start, i)) { // 从i位置砍一刀
                path.push_back(s.substr(start, i - start + 1));
                DFS(s, path, result, i + 1);  // 继续往下砍
                path.pop_back(); // 撤销上上行
            }
        }
    }
    bool isPalindrome(const string &s, int start, int end) {
        while (start < end && s[start] == s[end]) {
            ++start;
            --end;
        }
        return start >= end;
    }
};

代码3

// LeetCode, Palindrome Partitioning
// 动规,时间复杂度O(n^2),空间复杂度O(1)
class Solution {
public:
    vector<vector<string> > partition(string s) {
        const int n = s.size();
        bool p[n][n]; // whether s[i,j] is palindrome
        fill_n(&p[0][0], n * n, false);
        for (int i = n - 1; i >= 0; --i)
            for (int j = i; j < n; ++j)
                p[i][j] = s[i] == s[j] && ((j - i < 2) || p[i + 1][j - 1]);

        vector<vector<string> > sub_palins[n]; // sub palindromes of s[0,i]
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j)
                if (p[i][j]) {
                    const string palindrome = s.substr(i, j - i + 1);
                    if (j + 1 < n) {
                        for (auto v : sub_palins[j + 1]) {
                            v.insert(v.begin(), palindrome);
                            sub_palins[i].push_back(v);
                        }
                    } else {
                        sub_palins[i].push_back(vector<string> { palindrome });
                    }
                }
        }
        return sub_palins[0];
    }
};

Java代码:

 public class Solution {

    private void init(boolean[][] isPal, String s) {
        int len = isPal.length;
        for (int i=0; i<len; i++) isPal[i][i] = true;
        for (int k=1; k<len; k++)
            for (int i=0; i+k<len; i++) {
                if (s.charAt(i) != s.charAt(i+k)) continue;
                isPal[i][i+k] = (i+1 <= i+k-1) ? isPal[i+1][i+k-1] : true;
            }
    }

    private void helper(String s, int start, List<String> tmpPartition, List<List<String>> ans, boolean[][] isPal) {
        if (start >= s.length()){
        	ans.add(new ArrayList<String>(tmpPartition));
        	return;
        }
        for (int i=start; i< s.length(); i++) {
            if (isPal[start][i]) {
            	tmpPartition.add(s.substring(start, i+1));
                helper(s, i+1, tmpPartition, ans, isPal);
                tmpPartition.remove(tmpPartition.size() - 1);
            }
        }
    }

    public List<List<String>> partition(String s) {
        int len = s.length();
        boolean[][] isPal = new boolean[len][len];
        init(isPal, s);
        List<List<String>> ans = new ArrayList<List<String>>();
        List<String> tmpPartition = new ArrayList<String>();
        helper(s, 0, tmpPartition, ans, isPal);
        return ans;
    }
}

相关题目
Palindrome Partitioning II


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。