Leetcode刷题java之131. 分割回文串（一天一道编程题之第十四天）

我不是女神ヾ 2023-07-11 11:18 66阅读 0赞

执行结果：

通过

显示详情

执行用时 :5 ms, 在所有 Java 提交中击败了49.84% 的用户

内存消耗 :42.5 MB, 在所有 Java 提交中击败了5.10%的用户

题目：

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

输入: "aab"  
输出:  
\[  
\["aa","b"\],  
\["a","a","b"\]  
\]

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/palindrome-partitioning  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

采用回溯法，和一般的回溯法相同，只不过在遍历的过程中加一个判断回文的操作，将回文的加入。

代码：

class Solution {
        List<List<String>> result=new ArrayList<>();
        public List<List<String>> partition(String s) {
            if(s.length()==0||s==null)
            {
                return result;
            }
            LinkedList<String> track=new LinkedList<>();
            backtrack(s,0,s.length(),track);
            return result;
        }
        public void backtrack(String s,int start,int len,LinkedList<String> track)
        {
            if(start==len)
            {
                result.add(new LinkedList<>(track));
                return;
            }
            for(int i=start;i<len;i++)
            {
                if(!help(s,start,i))
                {
                    continue;
                }
                track.add(s.substring(start,i+1));
                backtrack(s,i+1,len,track);
                track.removeLast();
            }
        }
        public boolean help(String s,int left,int right)
        {
            while(left<=right)
            {
                if(!(s.charAt(left)==s.charAt(right)))
                {
                    return false;
                }
                left++;
                right--;
            }
            return true;
        }
    }