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構成的子串為回文子串，則很容易得到狀態轉移方程及邊界條件如下：

代碼實作

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()
    }
  }
}

標籤：其他

上一篇：不復雜的時間復雜度

下一篇：Minecraft-1.16.2-資料包開發學習#1