0131. Palindrome Partitioning (M)

Palindrome Partitioning (M)

题目

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

Return all possible palindrome partitioning of s.

Example:

Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

---

题意

对给定字符串进行划分，使其分出的每一部分都是一个回文子串。求出所有这样的划分方式。

思路

DFS处理。

可以利用动态规划对判断回文这一步骤进行优化：设若P[i][j]==true，则字符串s中从下标i到下标j构成的子串为回文子串，则很容易得到状态转移方程及边界条件如下：

\[P[i][j] = (P[i+1][j-1] \ \&\&\ s[i] == s[j]) \]

\[P[i][j] = \begin{cases} true, &i==j\ true, &j==i+1 \ \&\&\ s[i]==s[j]\ false, &j==i+1 \ \&\&\ s[i]\ !=s[j] \end{cases} \]

---

代码实现

Java

暴力递归

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> ans = new ArrayList<>();
        dfs(s, ans, new ArrayList<>());
        return ans;
    }

    private void dfs(String s, List<List<String>> ans, List<String> temp) {
        if (s.equals("")) {
            ans.add(new ArrayList<>(temp));
            return;
        }

        for (int i = 1; i <= s.length(); i++) {
            String sub = s.substring(0, i);
            if (isPalindrome(sub)) {
                temp.add(sub);
                dfs(s.substring(i), ans, temp);
                temp.remove(temp.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}

动态规划优化

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> ans = new ArrayList<>();
        boolean[][] dp = new boolean[s.length()][s.length()];
        
        // 生成dp数组
        for (int len = 1; len <= s.length(); len++) {
            for (int i = 0; i + len - 1 < s.length(); i++) {
                int j = i + len - 1;
                if (len == 1) {
                    dp[i][j] = true;
                } else if (len == 2) {
                    dp[i][j] = s.charAt(i) == s.charAt(j);
                } else {
                    dp[i][j] = dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
                }
            }
        }
        
        dfs(s, dp, 0, ans, new ArrayList<>());
        
        return ans;
    }

    private void dfs(String s, boolean[][] dp, int start, List<List<String>> ans, List<String> temp) {
        if (start == s.length()) {
            ans.add(new ArrayList<>(temp));
            return;
        }

        for (int end = start; end < s.length(); end++) {
            if (dp[start][end]) {
                temp.add(s.substring(start, end + 1));
                dfs(s, dp, end + 1, ans, temp);
                temp.remove(temp.size() - 1);
            }
        }
    }
}

JavaScript

/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function (s) {
  let ans = []
  let judge = new Array(s.length).fill(0).map(item => new Array(s.length).fill(false))

  for (let len = 1; len <= s.length; len++) {
    for (let left = 0; left + len - 1 < s.length; left++) {
      let right = left + len - 1
      if (left === right) {
        judge[left][right] = true
      } else if (right === left + 1) {
        judge[left][right] = s[left] === s[right]
      } else {
        judge[left][right] = judge[left + 1][right - 1] && s[left] === s[right]
      }
    }
  }

  dfs(s, 0, judge, ans, [])
  return ans
}

let dfs = function (s, start, judge, ans, tmp) {
  if (start === s.length) {
    return ans.push([...tmp])
  }

  for (let end = start; end < s.length; end++) {
    if (judge[start][end]) {
      tmp.push(s.slice(start, end + 1))
      dfs(s, end + 1, judge, ans, tmp)
      tmp.pop()
    }
  }
}