day-48 分割回文串

思路
利用dfs算法，用ids表示当前所指向字符的位置，依次判断s.charAt(ids),s.charAt(ids)+s.charAt(ids+1)…是否为回文字符串，如果是则加入链表p,再递归调用dfs函数

解题过程
每次调用dfs函数后记得还原现场

Code

class Solution {

    public String ss;
    public int len;
    public List<List<String>> list=new ArrayList<>();
    public List<List<String>> partition(String s) {

        ss=s;
        len=s.length();
        List<String> p=new ArrayList<>();
        dfs(p,0);
        return list;

    }

    public void dfs(List<String> p,int ids){

        if(ids==len){

            list.add(new ArrayList(p));
            return;
        }
        String t="";
        for(int i=ids;i<len;i++){

            t+=ss.charAt(i);
            if(isTrue(t)){

                p.add(t);
                dfs(p,i+1);
                p.remove(p.size()-1);
            }
        }
    }

    public boolean isTrue(String str) {

        int len = str.length();
        for (int i = 0; i < len / 2; i++) {

            if (str.charAt(i) != str.charAt(len - 1 - i)) {

                return false;
            }
        }
        return true;
    }

}

作者：菜卷
链接：https://leetcode.cn/problems/palindrome-partitioning/solutions/2903400/fen-ge-hui-wen-chuan-by-ashi-jian-chong-bap36/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

原文链接: https://blog.csdn.net/qq_53568730/article/details/141870136

目录