面试题——查找字符串中的所有的回文子串

思路

1、暴力法O(n^3)+O(n) 遍历字符串中所有的子串组合，判断每个子串是否是回文串。 其中遍历需要2层循环，判断回文串函数也是一层循环，故时间复杂度是O(n^3)。每次判断需要存储子串的内容，需要空间复杂度O(n)。

2、中心拓展法O(n^2) 遍历一遍字符串，以下标为中心，考虑子串长度是奇数或偶数，在这两种情况下拓展子串，判断子串是否是回文串。 假设子串长度是奇数，选择一个字符为中心，向两边扩展进行判断。 假设子串长度是偶数，选择两个字符为中心，向两边扩展进行判断。 一层遍历，一层判断，时间复杂度是O(n^2)。也需要存储子串的内容，空间复杂度O(n)。

暴力法O(n^3)+O(n)

public static ArrayList<String> findAllHuiWen1(String s){
    ArrayList<String> list = new ArrayList<String>();
    if(s==null || s.length()==0) return list;
    for(int i=0; i<s.length(); i++){
        for(int j=i+1; j<=s.length(); j++){
            String subString = s.substring(i, j);
            if(isHuiWen(subString) && !list.contains(subString))
                list.add(subString);
        }
    }
    return list;
}

public static boolean isHuiWen(String s){
    if(s==null || s.length()==0) return false;
    char[] arr = s.toCharArray();
    int left = 0;
    int right = arr.length-1;
    while (left<right){
        if(arr[left++] != arr[right--])
            return false;
    }
    return true;
}

用例

用例1 cabccbaa字符串中所有的回文子串：[c, a, abccba, b, bccb, cc, aa] 用例2 abc字符串中所有的回文子串：[a, b, c]

中心拓展法O(n^2)

public static ArrayList<String> findAllHuiWen2(String s){
    ArrayList<String> list = new ArrayList<String>();
    if(s==null || s.length()==0) return list;
    if(s.length()==1) {
        list.add(s);
        return list;
    }
    for(int i=0; i<s.length(); i++){
        getSubList(s,i,i,list);
        getSubList(s,i,i+1,list);
    }
    return list;
}

public static void getSubList(String s, int left, int right, ArrayList<String> list){
    while (left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)){
        String subString = s.substring(left, right+1);
        if(!list.contains(subString))
            list.add(subString);
        left--;
        right++;
    }
}

用例

用例1 cabccbaa字符串中所有的回文子串：[c, a, b, cc, bccb, abccba, aa] 用例2 abc字符串中所有的回文子串：[a, b, c]