国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

131. Palindrome Partitioning and 140. Word Break I

stonezhu / 925人閱讀

摘要:找到開頭的某個進(jìn)行切割。剩下的部分就是相同的子問題。記憶化搜索,可以減少重復(fù)部分的操作,直接得到后的結(jié)果。得到的結(jié)果和這個單詞組合在一起得到結(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++){
            // 找到開頭的某個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){
            // 如果這個單詞可以作為開頭,把剩下的部分作為完全相同的子問題。
            // 得到的結(jié)果和這個單詞組合在一起得到結(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)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/66918.html

相關(guān)文章

  • [LintCode] Palindrome Partitioning II

    摘要:假設(shè)我們從后向前,分析到第位,開始判斷,若為,說明從第位向前到第位的子串是一個回文串,則就等于第位的結(jié)果加。然后讓繼續(xù)增大,判斷第位到最后一位的范圍內(nèi),有沒有更長的回文串,更長的回文串意味著存在更小的,用新的來替換。 Problem Given a string s, cut s into some substrings such that every substring is a p...

    funnyZhang 評論0 收藏0
  • [leetcode]132. Palindrome Partitioning II

    摘要:用表示當(dāng)前位置最少需要切幾次使每個部分都是回文。表示到這部分是回文。如果是回文,則不需重復(fù)該部分的搜索。使用的好處就是可以的時間,也就是判斷頭尾就可以確定回文。不需要依次檢查中間部分。 Given a string s, partition s such that every substring of the partition is a palindrome. Return the...

    Airy 評論0 收藏0
  • [Leetcode] Palindrome Partitioning 回文分割

    摘要:深度優(yōu)先搜素復(fù)雜度時間空間思路因為我們要返回所有可能的分割組合,我們必須要檢查所有的可能性,一般來說這就要使用,由于要返回路徑,仍然是典型的做法遞歸時加入一個臨時列表,先加入元素,搜索完再去掉該元素。 Palindrome Partitioning Given a string s, partition s such that every substring of the parti...

    leanote 評論0 收藏0
  • leetcode132. Palindrome Partitioning II

    摘要:題目要求現(xiàn)在有一個字符串,將分割為多個子字符串從而保證每個子字符串都是回數(shù)。我們只需要找到所有可以構(gòu)成回數(shù)的并且得出最小值即可。即將字符作為,將字符所在的下標(biāo)列表作為。再采用上面所說的方法,利用中間結(jié)果得出最小分割次數(shù)。 題目要求 Given a string s, partition s such that every substring of the partition is a ...

    jeyhan 評論0 收藏0
  • [LintCode] Palindrome Partitioning

    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...

    NicolasHe 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<