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が提供する関数で文字列を反転して比較する方法もありますが、次の方法もあります.
5.計算を開始する前に、2次元配列に各サブ文字列(start,end)が返信文であるかどうかを設定します.
回答:
タイトルの説明:
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);
}
}