友链
姚屹晨

leetcode - [131] Palindrome Partitioning

2020/06/19

问题描述

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

Return all possible palindrome partitioning of s.

计算将一个字符串拆分成多个回文子字符串的组合数量。

举个例子：

Update at 2020_0908

关键在于判断u ~ i的子串是否回文。

来看下示意图：


再来看下实现：

class Solution {

    List<List<String>> ans = new LinkedList<>();

    private boolean isPalin(String s, int l, int r){
        if (l > r) return false;
        while (l < r){
            if (s.charAt(l) != s.charAt(r)) return false;
            l++;
            r--;
        }
        return true;
    }

    private void dfs(String s, LinkedList<String> child, int u){
        if (u == s.length()){
            ans.add(new LinkedList<>(child));
            return;
        }

        for (int i = u; i < s.length(); i++){
            if (isPalin(s, u, i)){
                child.add(s.substring(u, i + 1));
                dfs(s, child, i + 1);
                child.removeLast();
            }
        }
    }

    public List<List<String>> partition(String s) {
        dfs(s, new LinkedList<>(), 0);
        return ans;
    }
}

我们可以提前判断i ~ j子串是否回文，从而构建一个布尔矩阵。

i ~ j为回文需要满足两个条件：

第一：i和j对应的字符相等。

第二：其内部子串也回文。

来看下示意图：

再来看下实现：

class Solution {

    List<List<String>> ans = new LinkedList<>();
    boolean[][] f;

    private void dfs(String s, LinkedList<String> child, int u){
        if (u == s.length()){
            ans.add(new LinkedList<>(child));
            return;
        }

        for (int i = u; i < s.length(); i++){
            if (f[u][i]){
                child.add(s.substring(u, i + 1));
                dfs(s, child, i + 1);
                child.removeLast();
            }
        }
    }

    public List<List<String>> partition(String s) {
        int n = s.length();
        f = new boolean[n][n];
        // 1. 初始化f, f[i][j]表示该段子字符串是否回文
        for (int j = 0; j < n; j++){
            for (int i = 0; i <= j; i++){
                if (i == j) f[i][j] = true;
                if (s.charAt(i) == s.charAt(j)){
                    // 1.1 i + 1 > j - 1说明该子串仅有两个相等的字符
                    // 1.2 f[i + 1][j - 1] = true说明其内部为回文子串[除去两端相等的字符]
                    if (i + 1 > j - 1 || f[i + 1][j - 1]){
                        f[i][j] = true;
                    }
                }
            }
        }

        // 2. dfs
        dfs(s, new LinkedList<>(), 0);
        return ans;
    }
}

解法1

Thanks @issac3

来看示意图：

首先，我们需要什么东西？

我们需要一个存储最终结果的嵌套列表ans，一个存储字符串的临时列表child，

还有一个指向字符串s的当前索引start。

然后，如何判断一个字符串是否回文？

private boolean isPalindrome(String s, int lo, int hi){
    while (lo < hi){
        if (s.charAt(lo++) != s.charAt(hi--)){
            return false;
        }
    }
    return true;
}

注意，只有当目前的子字符串为回文时，才会继续往下递归遍历。否则，直接跳过。

最后，再来考虑下什么时候将满足条件的子列表加入结果列表？

当start索引指向字符串的最后一个字符的后一位：

if (start == s.length()){
    ans.add(new LinkedList<>(child));
}

来看下完整实现：

class Solution {
    public List<List<String>> partition(String s) {
        
        List<List<String>> ans = new LinkedList<>();
        bt(s, ans, new LinkedList<>(), 0);
        return ans;
    }
    
    private void bt(String s, List<List<String>> ans, LinkedList<String> child, int start){
        
        if (start == s.length()){
            ans.add(new LinkedList<>(child));
        }
        
        for (int i = start; i < s.length(); i++){
            if (isPalindrome(s, start, i)){
                child.add(s.substring(start, i + 1));
                bt(s, ans, child, i + 1);
                child.removeLast();
            }
        }
    }
    
    private boolean isPalindrome(String s, int lo, int hi){
        while (lo < hi){
            if (s.charAt(lo++) != s.charAt(hi--)){
                return false;
            }
        }
        return true;
    }
}

Enjoy it !


一位喜欢提问、尝试的程序员

（转载本站文章请注明作者和出处 姚屹晨-yaoyichen）

Post Directory