剑指offer86:分割回文子字符串

题目:
给定一个字符串 s ,请将 s 分割成一些子串,使每个子串都是 回文串 ,返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。

输入:s = “google”
输出:[[“g”,“o”,“o”,“g”,“l”,“e”],[“g”,“oo”,“g”,“l”,“e”],[“goog”,“l”,“e”]]

输入:s = “aab”
输出:[[“a”,“a”,“b”],[“aa”,“b”]]

输入:s = “a”
输出:[[“a”]]
提示:

1 <= s.length <= 16
s 仅由小写英文字母组成
分析:
输入字符串“google”,假设处理到第一个字符‘g’,此时包括字符‘g’在内后面一共有6个字符,所以此时面临6个选项,也就是分割出6个以字符‘g’开头的子字符串,分别是g,go,goo,goog,googl,google。其中只有g和goog是回文子字符串,再用同样的方法分割后面的字符串。
解决这个问题同样需要很多步,每一步分割出一个回文子字符串,如果处理到某个字符时包括该字符在内后面有n个字符,就面临n个选项。
具体细节见代码
代码:

import java.util.LinkedList;
import java.util.List;

public class Partition {
    public static void main(String[] args) {
        Partition partition = new Partition();
        String s = "google";
        List<List<String>> partition1 = partition.partition(s);
        System.out.println(partition1);
    }
    public List<List<String>> partition(String s) {
            LinkedList<List<String>> result = new LinkedList<>();
            //第一个参数是字符串,第二个参数是起始位置
            helper(s,0,new LinkedList<>(),result);
            return result;
    }

    private void helper(String str, int start, LinkedList<String> substrings, LinkedList<List<String>> result) {
        if (start == str.length()){
            result.add(new LinkedList<>(substrings));
            return;
        }
        //i从下标start开始,到字符串s的最后一个字符结束的每个子字符串是否为回,如果是回文就分割出一个符合条件的子字符串,添加到substrings          
        //中,接着处理下标从i+1开始的剩余的字符串,当start等于字符串s的长度时,整个字符串s已经被分割成若干回文字符串。
        for (int i = start; i < str.length(); i++) {
            if (isPalindrome(str,start,i)){
            //已经判断是回文字符串了
                substrings.add(str.substring(start,i+1));
                helper(str,i+1,substrings,result);
                substrings.removeLast();
            }
        }
    }
//判断是否是回文字符串
    private boolean isPalindrome(String str, int start, int end) {
    //首尾指针分别指向字符串的首部尾部,然后相向同时遍历,比较两个指针指向的字符是否相同,如果相同则接着遍历,不同则直接返回false,直到遍历完
    //字符串,最终返回true,证明是回文字符串
        while (start<end){
            if (str.charAt(start++) !=str.charAt(end--)){
                return false;
            }
        }
        return true;
    }
}

剑指offer86:分割回文子字符串

上一篇:第 14 章集合


下一篇:LinkedList方法(可实现栈和队列)