8000 added 116. Word Break · lixinsu/LeetCode@dd4c6e8 · GitHub
[go: up one dir, main page]
Skip to content 8000

Commit dd4c6e8

Browse files
pezypezy
committed
added 116. Word Break
1 parent 5075945 commit dd4c6e8

File tree

3 files changed

+153
-0
lines changed

3 files changed

+153
-0
lines changed

‎116. Word Break/README.md

Lines changed: 95 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,95 @@
1+
"LeetCode" ["Leet", "Code"]
2+
^^^^
3+
4+
拿到 dict 和 word, 如何确定是否正好可以 break? 题目中给的例子，判断起来很简单，首先从 word 的第一个字母开始迭代，迭代到 pos == 3 的位置时，发现 "Leet" 在 dict 中有记录，那么继续从 pos == 4 开始迭代，到 pos == 7 的时候，发现 "Code" 也在 dict 中有记录。此时，迭代已经走到 word 的末尾，恰好结束。可以认为 break 成功。
5+
6+
整理一下上述的思路，即为：
7+
8+
```cpp
9+
auto subBeg = s.cbegin();
10+
for (auto subEnd = subBeg; subEnd != s.cend(); ++subEnd)
11+
if (dict.find(string(subBeg, subEnd)) != dict.end()) subBeg = subEnd;
12+
// ^^^^^^^^^^^^^^^
13+
return dict.find(string(subBeg, s.cend())) != dict.end();
14+
```
15+
< 8000 /code>16+
短短四行，跑通上面的例子完全不成问题。
17+
18+
但这段代码的逻辑硬伤在于 subBeg 每一次找到后便立即后移，会错失一些子串的匹配，如何理解？看例子：
19+
20+
"aaaaaaa", ["aaaa", "aaa"]
21+
^^^```^
22+
23+
按照上述代码的逻辑，最终会返回 false, 因为每一次查找的都是 "aaa", 最终剩下的 "a" 无法匹配。在这个特殊例子里，"aaaa" 的子串，永远无法被验证。
24+
25+
这时候想，都是讨厌的 "aaa" 碍事，能否每次 find 成功后将其 key 在 dict 里删掉？貌似这样的确可以跑通了。
26+
27+
但如果 dict 里的某一个 key 真的就需要反复多次出现以拼成 s 呢？如以下例子：
28+
29+
"bb", ["a", "b"]
30+
^`
31+
32+
可以发现，如果我们匹配上第一个 "b", 继而删除之，那么第二个 "b" 将永远无法匹配，从而被认为是 false, 大错特错了。
33+
34+
真烦，删除肯定是走不通了，那我们笨一点，每一次 find 成功之后，都去多看一眼，后面剩下的子串能否也 find 上，如果可以，直接就返回 true 了。
35+
36+
```cpp
37+
auto subBeg = s.cbegin();
38+
for (auto subEnd = subBeg; subEnd != s.cend(); ++subEnd)
39+
if (dict.find(string(subBeg, subEnd)) != dict.end()) {
40+
subBeg = subEnd;
41+
if (dict.find(string(subBeg, s.cend())) != dict.end()) return true;
42+
}
43+
return false;
44+
```
45+
46+
虽然有点狗尾续貂的感觉，但的确好使，上述的全部用例都能一次性通过。
47+
48+
当然，对于一些特殊情况，如：
49+
50+
"a", ["a"]
51+
^
52+
53+
需要做特殊判断：
54+
55+
if (dict.find(s) != dict.end()) return true;
56+
57+
但这样就能躲过最开始我们讲述的硬伤了吗？譬如如下用例：
58+
59+
"goalspecial", ["go","goal","goals","special"]
60+
^^^^^^^^^
61+
62+
按照上述代码逻辑，首先匹配上 "go", 然后 `subBeg` 就已经后移至 'a', 这部分子串，无论如何也是匹配不上了，但如果一开始是分割成："goal" + "special", 那么恰好匹配上。
63+
64+
经过这么多用例的摧残，我们应该可以感受到**硬伤**到底在何处了。第一次 find 成功，应该产生两条备选方案：
65+
66+
1. `subEnd` 继续后移，继续尝试匹配。
67+
2. `subBeg` 后移，继续尝试匹配。
68+
69+
每一次 find 成功，都有这两个分支。那么我们有一个很自然的思路，就是：在这次迭代里不动 `subBeg`，让这一次迭代继续，每一次 find 成功，我们都将此刻的 `subEnd` 给记录下来。下一次迭代，直接从记录的 `subEnd` 开始。这样，就不会有所遗漏了。
70+
71+
当然，每一次迭代，我们都会立刻判断剩下的子串，是否能够匹配，如果可以，直接返回 true, 这一点逻辑不变。
72+
73+
故，我们需要一个容器来存储 `subEnd`, 代码如下：
74+
75+
```cpp
76+
if (dict.find(s) != dict.end()) return true;
77+
78+
std::vector<string::const_iterator> cache{s.cbegin()};
79+
80+
for (auto subEnd = s.cbegin(); subEnd != s.cend(); ++subEnd)
81+
82+
for (auto subBeg : cache)
83+
84+
if (subBeg < subEnd && dict.find(string(subBeg, subEnd)) != dict.end()) {
85+
86+
if (dict.find(string(subEnd, s.cend())) != dict.end()) return true;
87+
88+
cache.push_back(subEnd); break;
89+
90+
}
91+
92+
return false;
93+
```
94+
95+
提交，AC.

‎116. Word Break/TEST.cc

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
#define CATCH_CONFIG_MAIN
2+
#include "../Catch/single_include/catch.hpp"
3+
#include "solution.h"
4+
5+
TEST_CASE("Maximal Rectangle", "[maximalRectangle]")
6+
{
7+
Solution s;
8+
SECTION( "Example" )
9+
{
10+
std::unordered_set<std::string> uset{"Leet", "Code"};
11+
REQUIRE( s.wordBreak("LeetCode", uset) );
12+
}
13+
SECTION( "CASE0" )
14+
{
15+
std::unordered_set<std::string> uset{"aaaa", "aaa"};
16+
REQUIRE( s.wordBreak("aaaaaaa", uset) );
17+
}
18+
SECTION( "CASE1" )
19+
{
20+
std::unordered_set<std::string> uset{"a","b","bbb","bbbb"};
21+
REQUIRE( s.wordBreak("bb", uset) );
22+
}
23+
SECTION( "CASE2" )
24+
{
25+
9E88 std::unordered_set<std::string> uset{"a"};
26+
REQUIRE( s.wordBreak("a", uset) );
27+
}
28+
SECTION( "CASE3" )
29+
{
30+
std::unordered_set<std::string> uset{"go","goal","goals","special"};
31+
REQUIRE( s.wordBreak("goalspecial", uset) );
32+
}
33+
SECTION( "CASE4" )
34+
{
35+
std::unordered_set<std::string> uset{"aaaa", "aa"};
36+
REQUIRE_FALSE( s.wordBreak("aaaaaaa", uset) );
37+
}
38+
}

‎116. Word Break/solution.h

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
#include <string>
2+
using std::string;
3+
#include <unordered_set>
4+
using std::unordered_set;
5+
#include <vector>
6+
7+
class Solution {
8+
public:
9+
bool wordBreak(string s, unordered_set<string> &dict) {
10+
if (dict.find(s) != dict.end()) return true;
11+
std::vector<string::const_iterator> cache{s.cbegin()};
12+
for (auto subEnd = s.cbegin(); subEnd != s.cend(); ++subEnd)
13+
for (auto subBeg : cache)
14+
if (subBeg < subEnd && dict.find(string(subBeg, subEnd)) != dict.end()) {
15+
if (dict.find(string(subEnd, s.cend())) != dict.end()) return true;
16+
cache.push_back(subEnd); break;
17+
}
18+
return false;
19+
}
20+
};

0 commit comments

Comments
 (0)
0