【leetcode】分割エコー列Java実装

タイトル:
文字列sが与えられ、sはいくつかのサブストリングに分割され、各サブストリングがエコーストリングであるようにする.
sの可能なすべての分割スキームを返します.
例:
入力: 「aab」出力:[  ["aa","b"],   ["a","a","b"] ]
問題解決の考え方:
もう少し長い例を挙げましょう.例えばaabcc、私が最初に見た後、私の普通の人間の頭で案を並べ始めました.
個々の文字は回文列です:a|abcc
次にabccを分析し、単独で1つのaを切るのは回文である:a|bcc、(ab,abc,abccはいずれも回文ではないので、この3つの切法を考慮しない(従ってabccについてはa|bccである)
更にbccは、単独のbが回文である:b|cc、(bc,bccも回文ではない(従ってbccについてはb|ccの一種である
最後にccは、単独のcが回文である:c|c、または2つのcも回文を構成する:cc|
c|cの中で、后ろのこのc、更にそれを切ってc|なので、今cc|と同じように最后まで分けて、"|"の后ろは空です.
整理すると、「a,b,c,c」と「a,b,cc」は今回の結果ですが、まだ終わっていません!
aの後ろから分割するので、次にaa|bcc,aab|cc,aabc|c,aabcc|の角度から切ることができ、毎回固定|の前の部分を切るたびに、同じ切欠法で|後ろの部分を分析することができる.
ここまで来ると何かインスピレーションがあったようですね~
毎回最初から遍歴して、1つの文字の2つの文字の3つの文字はこのように検査して、1段の回文ならばそれでは切って、接点の後ろの部分は同じ方法で使います;
接点が空いていれば空リストを返し、戻る異なるルートで前のカットをこのリストの前に付けて、ルートの最初に戻るのが結果です.
表現力が少し鶏を捕まえるが、とにかく最初から最後まで切って、最後から最後まで添える過程で、科学的には「分治」という.大きな文字列を小さな文字列に切り、小さな文字列を空に切る.
反復(スタック)または再帰的な方法を使用できます.
JAVAコードを貼り付けます.

class Solution {
    public List> partition(String s) {
        boolean[][] dp=new boolean[s.length()][s.length()];
        for(int len=1;len<=s.length();len++){
            for(int i=0;i<=s.length()-len;i++){
                if(len==1)dp[i][i]=true;
                else if(s.charAt(i)==s.charAt(i+len-1)&&(len==2||dp[i+1][i+len-2])){
                    dp[i][i+len-1]=true;
                }
            }
        }
        return solution(s,0,dp);
    }
    public List> solution(String s,int start,boolean[][] dp){
        ArrayList> list=new ArrayList<>();
        if(start==s.length()){//      ，      list，        
            List li=new ArrayList<>();
            list.add(li);
            return list;
        }
        for(int i=start;i li:solution(s,i+1,dp)){
                    li.add(0,first);//          list            
                    list.add(li);
                }
            }
        }
        return list;
    }
    
}

PS:ここでは、stringの一節が返信文かどうかを判断しやすいように、事前にダイナミックプランニング法でdp配列を作り、この一節が返信文であればtrueと記録します.
1、回文長lenは1、2、3、4、...、lengthである.
2、回文の起点iは0、1、2、3、...、length-len(後の長さがlen未満であればlen長の回文ではないに違いない).
3、長さlenが1であれば、1文字になるのは返事に違いない.
もし長さが2で、起点の文字==終点の文字であれば、起点は終点に隣接していて、彼ら二人はまだ等しいので、それは安定しています.
長さが2より大きく、始点の文字==終点の文字であれば、内層が回文であれば回文であり、dp[i+1][i+len-2]は始点+1から終点-1までの文字列が回文であるか否かを表す.
以上、問題があれば批判を歓迎します.
 
本菜鳥のブログ園https://www.cnblogs.com/zhangmora/p/LC131.html