`
cozilla
  • 浏览: 92071 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

[Leetcode] Word Break 1 & 2

 
阅读更多

Word Break

 
AC Rate: 2/13
My Submissions

 

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

建字典树搞。

 

class Solution {
public:

    class Node {
    public:
        Node* next[26];
        bool end;
        Node(): end(false) { for (int i = 0; i < 26; i++) next[i] = NULL;}
        void insert(string a) {
            Node * cur = this;
            for (int i = 0; i < a.size(); i++) {
                if (cur->next[a[i]-'a'] == NULL) {
                    cur->next[a[i]-'a'] = new Node();
                }
                cur = cur->next[a[i]-'a'];
            }
            cur->end = true;
        }
        ~Node () {
            for (int i = 0;i < 26; i++) delete next[i];
        }
    };
    
    bool wordBreak(string s, unordered_set<string> &dict) {
        Node root;
        for (auto it = dict.begin(); it != dict.end(); ++it) {
            root.insert(*it);
        }
        
        vector<bool> v(s.size(), false);
        findMatch(s, &root, 0, v);
        for (int i = 0; i < s.size(); i++) 
            if (v[i]) findMatch(s, &root, i+1, v);
        return v[s.size() - 1];
    }
    
    void findMatch(const string& s, Node* cur, int start, vector<bool> &v) {
        int i = start, n = s.size();
        while (i < n) {
            if (cur->next[s[i] - 'a'] != NULL) {
                if (cur->next[s[i] - 'a']->end) v[i] = true;
                cur = cur->next[s[i] - 'a'];
            }
            else break;
            i++;
        }
        
    }
};

 

粗暴一点也是ok的。

class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        int n = dict.size();
        int maxlen = 0;
        for (auto it = dict.begin(); it != dict.end(); ++it) 
            if (it->size() > maxlen)   maxlen = it->size();
        int sn = s.size();
        vector<bool> v(sn, false);
        for (int i = 0; i < sn; i++) {
            if (i == 0 || (i > 0 && v[i-1])) {
                for (int j = 1; j <= maxlen && i + j - 1 < sn; j++) {
                    if (dict.count(s.substr(i,j)) > 0) v[i+j-1] = true;
                }
            }
        }
        return v[sn-1];
    }
};

 

 

Word Break II

 
AC Rate: 9/89
My Submissions

 

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

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

 

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        vector<string> res;
        int dn = dict.size();
        int sn = s.size();
        int maxlen = 0;
        for (auto it = dict.begin(); it != dict.end(); ++it) {
            if (it->size() > maxlen) maxlen = it->size();
        }
        vector<vector<int> > next(sn);
        vector<bool> v(sn, false);
        for (int i = 0; i < sn; i++) {
            if (i == 0 || (i > 0 && v[i-1])) {
                for (int j = 1; j <= maxlen && i+j-1 < sn; j++) {
                    if (dict.count(s.substr(i, j)) > 0) {
                        v[i+j-1] = true;
                        next[i].push_back(j);
                    }
                }
            }
        }
        if (!v[sn-1]) return res;
        vector<int> x;
        x.push_back(0);
        gen(s, res, next, x);
        
        return res;
    }
    
    void gen(const string& s, vector<string>& res, vector<vector<int> >& next, vector<int> &v) {
        int cur = v.back();
        if (cur == s.size()) {
            string t = s.substr(v[0], v[1] - v[0]);
            for (int i = 1; i < v.size() - 1; i++)
                t += " " + s.substr(v[i], v[i+1] - v[i]);
            res.push_back(t);
            return;
        }
        
        for (int i = 0; i < next[cur].size(); i++) {
            v.push_back(cur+next[cur][i]);
            gen(s, res, next, v);
            v.pop_back();
        }
    }
};

 

分享到:
评论

相关推荐

    python-leetcode题解之139-Word-Break

    python python_leetcode题解之139_Word_Break

    python-leetcode题解之140-Word-Break-II

    python python_leetcode题解之140_Word_Break_II

    js-leetcode题解之139-word-break.js

    javascript js_leetcode题解之139-word-break.js

    js-leetcode题解之140-word-break-ii.js

    javascript js_leetcode题解之140-word-break-ii.js

    LeetCode最全代码

    15 | [3 Sum](https://leetcode.com/problems/3sum/) | [C++](./C++/3sum.cpp) [Python](./Python/3sum.py) | _O(n^2)_ | _O(1)_ | Medium || Two Pointers 16 | [3 Sum Closest]...

    LeetCode题解(java语言实现).pdf

    * Word Break、Word Break II:该题目要求将字符串分割成单词,实现方法使用了动态规划和回溯算法。 * Word Ladder:该题目要求将一个单词转换成另一个单词,实现方法使用了广度优先搜索算法。 二、树和图 * ...

    leetcode苹果-word-break:断字

    1: Input: s = "leetcode", wordDict = ["leet", "code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code". Example 2: Input: s = "applepenapple", wordDict = [...

    Leetcode题目+解析+思路+答案.pdf

    - **Word Break**:判断一个字符串是否可以拆分为一个词汇表中的单词序列。 7. **链表(Linked List)**: - **Linked List Cycle**:检测链表中的环。 - **Remove Duplicates from Sorted List**:从已排序的...

    LeetCode题解 - Java语言实现-181页.pdf

    4. Solution Word Break 单词断词是一个自然语言处理问题,要求将字符串断词为单词。可以使用动态规划或Trie树来解决该问题。 5. Word Break II 单词断词II是一个变体的问题,要求将字符串断词为单词,并且可以...

    leetcode刷题之动态规划

    var wordBreak = function(s, wordDict) { let n = s.length; let dp = new Array(n + 1).fill(false); dp[0] = true; for (let i = 0; i ; i++) { for (let j = 0; j ; j++) { if (dp[j] && wordDict....

    javascript-leetcode面试题解动态规划问题之第139题单词拆分-题解.zip

    function wordBreak(s, wordDict) { const dp = Array(s.length + 1).fill(false); dp[0] = true; for (let i = 1; i ; i++) { for (const word of wordDict) { if (s.startsWith(word, i - word.length) && ...

    wordbreakleetcode-WordBreak-Leetcode-139:一种使用动态规划来确定一个词是否可以作为给定词典中所有词的串

    在提供的代码库"WordBreak-Leetcode-139-master"中,你可能会找到一个具体的实现,它可能包括以下部分: - 主函数,接收字符串sentence和词汇表wordDict作为输入参数。 - 动态规划的逻辑,包括初始化dp数组和遍历...

    python-leetcode面试题解之第139题单词拆分-题解.zip

    def wordBreak(s, wordDict): wordDict = set(wordDict) # 将单词列表转换为集合,加快查找速度 dp = [False] * (len(s) + 1) # 初始化动态规划数组,dp[i]表示s[:i]是否可以被拆分 dp[0] = True # 空字符串可以...

    uber leetcode

    - **题目描述:**给定两个字符串word1和word2,返回使word1和word2相同所需的最小步数。每步可以插入一个字符、删除一个字符或者替换一个字符。 - **应用场景:**自然语言处理中的拼写纠错、相似度比较等场景。 ...

    LeetCode:LeetCode解决方案

    preorder-traversal链表reorder-list链表linked-list-cycle-ii链表linked-list-cycle动态规划word-break-ii动态规划word-break链表copy-list-with-random-pointer复杂度single-number-ii复杂度single-number动态规划

    leetcode530-leetcode:力扣在线评委

    leetcode 530 力扣在线评委 # 问题 困难 解决方案 1 简单的 2 中等的 3 中等的 12 中等的 22 中等的 39 中等的 94 中等的 108 中等的 122 中等的 136 中等的 144 中等的 167 中等的 238 中等的 260 中等的 268 中等...

    leetcode338-coding_notebook:编码_笔记本

    Break](Leetcode 问题/数组和字符串/139.word_break.md) [140. Word Break ii](Leetcode 问题/数组和字符串/140.word_break_ii.md) [151. 反转字符串中的单词](Leetcode Problems/Array and String/151.reverse_...

    LintCode 582: Word Break II

    Word Break II Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences. Example Example 1...

    gasstationleetcode-leetcode:LeetcodeOJ解决方案

    leetcode 【演示记录】 报告 展示 2017/03/06 1.二和,167.二和二 2107/03/06 15.3 总和,16.3 总和最近,18.4 总和,11.最多水的容器 2017/03/09 62.Unique Paths, 63.Unique Paths II, 64.Minimum Path Sum 2017/...

    扩展矩阵leetcode-Leetcode:LeetcodeAnswer-Java

    扩展矩阵leetcode Leetcode Leetcode Answer-Java 数组 11.乘最多水容器 ...wordBreak 279.完全平方数 numSquares 排序 56.合并区间 merge 75.颜色分类 sortColors 179.最大数 largestNumber 324.摆

Global site tag (gtag.js) - Google Analytics