131. Palindrome Partitioning and 140. Word Break I

stonezhu 发布于2019-08-14 17:58 / 923人阅读

摘要：找到开头的某个进行切割。剩下的部分就是相同的子问题。记忆化搜索，可以减少重复部分的操作，直接得到后的结果。得到的结果和这个单词组合在一起得到结果。

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进行切割。
            // 剩下的部分就是相同的子问题。
            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){
        // 记忆化搜索，可以减少重复部分的操作，直接得到break后的结果。
        if(memo.containsKey(s)){
            return memo.get(s);
        }
        
        int n = s.length();
        List list = new ArrayList();
        for(String word: wordDict){
            // 如果这个单词可以作为开头，把剩下的部分作为完全相同的子问题。
            // 得到的结果和这个单词组合在一起得到结果。
            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;
    }
}

GPU云服务器云服务器 break-word word-break palindrome cdn140

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66918.html

[LintCode] Palindrome Partitioning II

摘要：假设我们从后向前，分析到第位，开始判断，若为，说明从第位向前到第位的子串是一个回文串，则就等于第位的结果加。然后让继续增大，判断第位到最后一位的范围内，有没有更长的回文串，更长的回文串意味着存在更小的，用新的来替换。 Problem Given a string s, cut s into some substrings such that every substring is a p...

funnyZhang 2019-08-14 15:30 评论0 收藏0
[leetcode]132. Palindrome Partitioning II

摘要：用表示当前位置最少需要切几次使每个部分都是回文。表示到这部分是回文。如果是回文，则不需重复该部分的搜索。使用的好处就是可以的时间，也就是判断头尾就可以确定回文。不需要依次检查中间部分。 Given a string s, partition s such that every substring of the partition is a palindrome. Return the...

Airy 2019-08-14 16:54 评论0 收藏0
[Leetcode] Palindrome Partitioning 回文分割

摘要：深度优先搜素复杂度时间空间思路因为我们要返回所有可能的分割组合，我们必须要检查所有的可能性，一般来说这就要使用，由于要返回路径，仍然是典型的做法递归时加入一个临时列表，先加入元素，搜索完再去掉该元素。 Palindrome Partitioning Given a string s, partition s such that every substring of the parti...

leanote 2019-08-14 12:32 评论0 收藏0
leetcode132. Palindrome Partitioning II

摘要：题目要求现在有一个字符串，将分割为多个子字符串从而保证每个子字符串都是回数。我们只需要找到所有可以构成回数的并且得出最小值即可。即将字符作为，将字符所在的下标列表作为。再采用上面所说的方法，利用中间结果得出最小分割次数。题目要求 Given a string s, partition s such that every substring of the partition is a ...

jeyhan 2019-08-15 14:27 评论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 2019-08-14 15:11 评论0 收藏0