leetcode 139.单词拆分 BFS

题目描述

leetcode 139.单词拆分

---

思路

• 维护一个队列，用指针描述一个节点。
• 起初，指针 0 入列，然后它出列，指针 1,2,3,4,5,6,7,8 是它的子节点，分别与 0 围出的前缀子串（左闭右开的围），是单词就让它入列，继续考察以它（右区间，即儿子）为起点的剩余子串；不是单词，对应的指针不入列
• 然后重复地做：节点（指针）出列，考察它的子节点，能入列的就入列、再出列……
• 直到指针越界，没有剩余子串了，没有指针可入列，如果前缀子串是单词，说明之前一直在切出单词，返回 true。
• 如果整个BFS过程，始终没有返回true，则返回 false。

---

代码

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> us(wordDict.begin(),wordDict.end()); //哈希集，存放字典中的所有单词
        vector<bool> visited(s.length(),false);  //判重数组，防止重复访问

        queue<int> q;  
        q.push(0);   //根节点为0

        while(!q.empty())
        {
            int start=q.front();
            q.pop();
            if(visited[start])   //如果之前访问过以start为起始点的串，则跳出去
                continue;
            visited[start]=true;  //标记为访问过

            for(int i=start+1;i<=s.length();i++)   //遍历右边的开区间
            {
                string str(s.begin()+start,s.begin()+i);  //把字符串取出来
                if(us.count(str))  //如果是单词
                {
                    if(i<s.length())  //继续往下去遍历判断
                        q.push(i);
                    else               //否则如果越界，最后还以单词结尾，则说明符合条件，返回true
                        return true;
                }
            }
        }
        return false;   //最后如果没返回true，说明不符合条件，返回false
    }
};
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

---