Word Break 问题

要求

给一串字符串和一个字典，判断这个字符串是否能够拆分成字典里面的词

例子

s = “wordbreakproblem”
dict = [“word”,“break”,“problem”,“big”,“other”]
s 可以拆分成"word",“break”,“problem”

做法

1. 初始化一个数组ve，假设字符串为"wordbreakproblem"，字典为[“word”,“break”,“problem”,“big”,“other”]，ve[1] = “"，表示字符串的子串"w"没有符合字典的单词，ve[4] = "word”,表示字符串子串"word"有第一个符合字典的单词"word",ve[8] = “break”,表示字符串子串"wordbreak"有第二个符合字典的单词"break"（因为word已经在之前记录了，所以在该子串不要记录）；
2. 遍历取字符串的子串，如果子串存在字典里面的单词，就在对应子串记录该单词，已经记录的单词就不再记录；

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;


class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        vector<string> ve;
        ve.resize(s.length()+1, "");
        for (int i=0; i<=s.length(); i++) {
            string word = s.substr(0,i);
            if (wordDict.count(word)>0) {
                ve[i] = word;
            }else{
                for (int j = 0; j<i; j++) {
                    if (ve[j]!="") {
                        string word = s.substr(j,i-j);
                        if (wordDict.count(word)>0) {
                            ve[i] = word;
                            break;
                        }
                    }
                }

            }

        }
        if (ve[s.length()]=="") {
            return false;
        }else{
            return true;
        }
    }
};

Comments