Leetcode OJ 131 Palindrome Partitioning [Medium]


Leetcode OJ 131 Palindrome Partitioning [Medium]
タイトルの説明:
Given a string s, partition s such thatevery substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab", Return
[
 ["aa","b"],
 ["a","a","b"]
]
タイトルの理解:
1つの文字列sが与えられ、sが分割され、各サブ文字列がエコーされ、可能なすべての分割が返される.
テスト例:
機能テスト:「aab」、「abb」など;
特殊入力:入力sはnull;sは1文字しかありません.
分析:
1.再帰(深度優先探索)+ループ
2.「aab」の処理:「a」は回文であり、ListsubStringに加え、「ab」を再処理し、subListに最近追加された要素を除去して続行する.次に「aa」は回文であり、subStringに加え、「b」を処理してsubListに最近追加された要素を除去してから続行する.次に「aab」は返事ではなく、subStringには参加しません.サイクル終了;
3.文字列の最後の1つが処理された場合、subStringをresultに追加します.
4.回文を判断する方法は、javaが提供する関数で文字列を反転して比較する方法もありますが、次の方法もあります.
public boolean isPalindrome(String s, int start, int end) {
         while(start < end) {
             if(s.charAt(start) != s.charAt(end)) {
                 return false;
             }
             start++;
             end--;
         }
         return true;
}

5.計算を開始する前に、2次元配列に各サブ文字列(start,end)が返信文であるかどうかを設定します.
 boolean[][] isPalindrome = new boolean[s.length()][s.length()];
        for (int start = s.length() - 1; start >= 0; start--) {
            for (int end = start; end < s.length(); end++) {
                if (end - start > 1) {
                    isPalindrome[start][end] = isPalindrome[start + 1][end - 1] && s.charAt(start) == s.charAt(end);
                } else {
                    isPalindrome[start][end] = s.charAt(start) == s.charAt(end);
                }
            }
        }

回答:
class Solution {
    public List> partition(String s) {
        char[] c = s.toCharArray();
        List> result = new ArrayList>();
        List subString = new ArrayList();
        recursion(s,result,subString,0);
        return result;
    }
    public void recursion(String s,List> result, List subString, int start){
        if(start == s.length()){
            result.add(new ArrayList(subString));

        }
        for(int end = start+1; end <= s.length(); end ++){
            String firstSubString = s.substring(start,end);
            if(isPalindrome(firstSubString)){
                subString.add(firstSubString);
                recursion(s,result,subString,end);
                subString.remove(subString.size() - 1);
            }
        }
    }
    public static boolean isPalindrome(String s){
        String rs = new StringBuilder(s).reverse().toString();
        return s.equals(rs);
    }
}