資訊專欄INFORMATION COLUMN
摘要：找到開頭的某個(gè)進(jìn)行切割。剩下的部分就是相同的子問題。記憶化搜索，可以減少重復(fù)部分的操作，直接得到后的結(jié)果。得到的結(jié)果和這個(gè)單詞組合在一起得到結(jié)果。
Given a string s, partition s such that every 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"] ]
public class Solution {
public List> partition(String s) {
List> res = new ArrayList>();
if(s == null || s.length() == 0) return res;
dfs(s, res, new ArrayList(), 0);
return res;
}
public void dfs(String s, List> res, List path, int pos){
if(pos == s.length()){
res.add(new ArrayList(path));
return;
}
for(int i = pos; i < s.length(); i++){
// 找到開頭的某個(gè)palindrome進(jìn)行切割。
// 剩下的部分就是相同的子問題。
if(isPalindrome(s, pos, i)){
path.add(s.substring(pos, i+1));
dfs(s, res, path, i+1);
path.remove(path.size()-1);
}
}
}
public boolean isPalindrome(String s, int i, int j){
while(i < j){
if(s.charAt(i++) != s.charAt(j--)) return false;
}
return true;
}
}
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words. Return all such possible sentences. For example, given s = "catsanddog", dict = ["cat", "cats", "and", "sand", "dog"]. A solution is ["cats and dog", "cat sand dog"].
public class Solution {
public List wordBreak(String s, List wordDict) {
return dfs(s, wordDict, new HashMap>());
}
public List dfs(String s, List wordDict, HashMap> memo){
// 記憶化搜索，可以減少重復(fù)部分的操作，直接得到break后的結(jié)果。
if(memo.containsKey(s)){
return memo.get(s);
}
int n = s.length();
List list = new ArrayList();
for(String word: wordDict){
// 如果這個(gè)單詞可以作為開頭，把剩下的部分作為完全相同的子問題。
// 得到的結(jié)果和這個(gè)單詞組合在一起得到結(jié)果。
if(!s.startsWith(word)) continue;
int len = word.length();
if(len == n){
list.add(word);
} else {
List sublist = dfs(s.substring(len), wordDict, memo);
for(String item: sublist){
list.add(word + " " + item);
}
}
}
memo.put(s, list);
return list;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66918.html
摘要：假設(shè)我們從后向前，分析到第位，開始判斷，若為，說明從第位向前到第位的子串是一個(gè)回文串，則就等于第位的結(jié)果加。然后讓繼續(xù)增大，判斷第位到最后一位的范圍內(nèi)，有沒有更長(zhǎng)的回文串，更長(zhǎng)的回文串意味著存在更小的，用新的來替換。 Problem Given a string s, cut s into some substrings such that every substring is a p...
摘要：用表示當(dāng)前位置最少需要切幾次使每個(gè)部分都是回文。表示到這部分是回文。如果是回文，則不需重復(fù)該部分的搜索。使用的好處就是可以的時(shí)間，也就是判斷頭尾就可以確定回文。不需要依次檢查中間部分。 Given a string s, partition s such that every substring of the partition is a palindrome. Return the...
摘要：深度優(yōu)先搜素復(fù)雜度時(shí)間空間思路因?yàn)槲覀円祷厮锌赡艿姆指罱M合，我們必須要檢查所有的可能性，一般來說這就要使用，由于要返回路徑，仍然是典型的做法遞歸時(shí)加入一個(gè)臨時(shí)列表，先加入元素，搜索完再去掉該元素。 Palindrome Partitioning Given a string s, partition s such that every substring of the parti...
摘要：題目要求現(xiàn)在有一個(gè)字符串，將分割為多個(gè)子字符串從而保證每個(gè)子字符串都是回?cái)?shù)。我們只需要找到所有可以構(gòu)成回?cái)?shù)的并且得出最小值即可。即將字符作為，將字符所在的下標(biāo)列表作為。再采用上面所說的方法，利用中間結(jié)果得出最小分割次數(shù)。 題目要求 Given a string s, partition s such that every substring of the partition is a ...
Problem Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. Example Given s = aab, return: [ [aa,b], [a,a,b...
閱讀 1272·2021-11-23 09:51
閱讀 2662·2021-09-03 10:47
閱讀 2244·2019-08-30 15:53
閱讀 2430·2019-08-30 15:44
閱讀 1383·2019-08-30 15:44
閱讀 1206·2019-08-30 10:57
閱讀 1936·2019-08-29 12:25
閱讀 1098·2019-08-26 11:57
