leetcode 131. 分割回文串

leetcode 131. 分割回文串

题目

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1：

输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]
示例 2：

输入：s = “a”
输出：[[“a”]]

提示：

1 <= s.length <= 16
s 仅由小写英文字母组成

思路

这题说实话，一开始合计的是一个个加进来，然后当前最后一个字符串加上新的字符是回文串就继续dfs，然后不管最后一个字符串加上新的字符是不是回文串这里都要断开。这样就能保证所有情况的覆盖，因此有了第一版代码。但这WA了。。。因为没考虑所谓回文串aba是回文串，新的字符是c可能不是回文串，但再往后加可能是abacaba，这又是回文串了。所以我们得考虑这种情况。于是有了第二版，AC了。看了剪枝操作，有了第三版，不用每次都判断回文串了，而是用一个数组存储各种情况，在本题中最长就16字符，所以效果不明显，之后这种空间换时间的思路还是要记得的。

题解

// 第一版
class Solution {
    List<List<String>> list = new ArrayList<>();
    List<String> subList = new ArrayList<>();
    boolean st[];

    public List<List<String>> partition(String s) {
        st = new boolean[s.length()];
        dfs(s, 0);
        return list;
    }

    public boolean isOk(String item, char i) {
        if (item.charAt(0) != i) {return false;}
        int st = 1, ed = item.length() - 1;
        while (st < ed) {
            if (item.charAt(st) != item.charAt(ed)) {return false;}
            st++;
            ed--;
        }
        return true;
    }

    public boolean gap(int idx) {
        for (int i=idx-1;i>-1;i--) {
            if (st[i] == false) {return true;}
        }
        return false;
    }

    public void dfs(String s, int idx) {
        if (idx == s.length()) {
            list.add(new ArrayList<>(subList));
            return;
        }
        for (int i=idx;i<s.length();i++) {
            if (gap(i)) {return;}
            if (subList.isEmpty())
            {
                subList.add(String.valueOf(s.charAt(i)));
                st[i] = true;
                dfs(s, i + 1);
                subList.remove(0);
                st[i] = false;
            }
            else if (isOk(subList.get(subList.size() - 1), s.charAt(i))) {
                String tmp = subList.get(subList.size() - 1);
                subList.remove(subList.size() - 1);
                subList.add(tmp + String.valueOf(s.charAt(i)));
                st[i] = true;
                dfs(s, i + 1);
                subList.remove(subList.size() - 1);
                subList.add(tmp);
                st[i] = false;
            }
            if (! subList.isEmpty()) {
                subList.add(String.valueOf(s.charAt(i)));
                st[i] = true;
                dfs(s, i + 1);
                subList.remove(subList.size() - 1);
                st[i] = false;
            }
        }
    }
}
// 第二版
class Solution {
    List<List<String>> list = new ArrayList<>();
    List<String> subList = new ArrayList<>();

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

    public boolean isOk(String item) {
        int st = 0, ed = item.length() - 1;
        while (st < ed) {
            if (item.charAt(st) != item.charAt(ed)) {return false;}
            st++;
            ed--;
        }
        return true;
    }

    public void dfs(String s, int idx) {
        if (idx == s.length()) {
            list.add(new ArrayList<>(subList));
            return;
        }
        for (int i=idx;i<s.length();i++) {
            String str = s.substring(idx, i + 1);
            if (isOk(str)) {
                subList.add(str);
                dfs(s, i + 1);
                subList.remove(subList.size() - 1);
            }
            else {continue;}

        }
    }
}
// 第三版
class Solution {
    List<List<String>> list = new ArrayList<>();
    List<String> subList = new ArrayList<>();
    // 空间换时间
    boolean[][] isPartition;

    public List<List<String>> partition(String s) {
        isPartition = new boolean[s.length()][s.length()];
        isOk(s);
        dfs(s, 0);
        return list;
    }

    public void isOk(String item) {
        for (int i=0;i<item.length();i++) {
            for (int j=i;j<item.length();j++) {
                int st = i, ed = j;
                while (st < ed) {
                    if (item.charAt(st) != item.charAt(ed)) {
                        break;
                    }
                    st++;
                    ed--;
                }
                if (st >= ed) {isPartition[i][j] = true;}
            }
        }      
    }

    public void dfs(String s, int idx) {
        if (idx == s.length()) {
            list.add(new ArrayList<>(subList));
            return;
        }
        for (int i=idx;i<s.length();i++) {
            // 基于当前subList已有的回文串，以及当前idx开始往后i - idx位，只要有回文串就放里
            if (isPartition[idx][i]) {
                String str = s.substring(idx, i + 1);
                subList.add(str);
                dfs(s, i + 1);
                subList.remove(subList.size() - 1);
            }
            else {continue;}
        }
    }
}