Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit120b32e

Browse files
authored
Merge pull request6boris#104 from kylesliu/develop
add 139 140 problem solution
2 parentsac87d9c +d1eef90 commit120b32e

File tree

6 files changed

+418
-0
lines changed

6 files changed

+418
-0
lines changed

‎src/0139.Word-Break/README.md

Lines changed: 115 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,115 @@
1+
#[139. Word Break][title]
2+
3+
##Description
4+
5+
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
6+
7+
##Note:
8+
9+
The same word in the dictionary may be reused multiple times in the segmentation.
10+
You may assume the dictionary does not contain duplicate words.
11+
12+
**Example 1:**
13+
14+
```
15+
Input: s = "leetcode", wordDict = ["leet", "code"]
16+
Output: true
17+
Explanation: Return true because "leetcode" can be segmented as "leet code".
18+
```
19+
20+
**Example 2:**
21+
22+
```
23+
Input: s = "applepenapple", wordDict = ["apple", "pen"]
24+
Output: true
25+
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
26+
Note that you are allowed to reuse a dictionary word.
27+
```
28+
29+
**Example 3:**
30+
31+
```
32+
Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
33+
Output: false
34+
```
35+
36+
37+
**Tags:** Math, String
38+
39+
##题意
40+
>给定一个非空字符串ss和一个非空词典wordDictwordDict,判断ss是否能被分割成一个或多个单词分隔的序列。
41+
>注意，词典中的词可以用多次，词典中没有重复的单词。
42+
43+
##题解
44+
45+
###思路1
46+
>动态规划
47+
48+
```go
49+
package main
50+
51+
funcwordBreak(sstring,wordDict []string)bool {
52+
dp:=make([]bool,len(s)+1)
53+
dp[0] =true
54+
55+
fori:=0; i <len(dp); i++ {
56+
if dp[i] {
57+
for_,word:=range wordDict {
58+
//巧妙的运用 i + word len 避免2层循环
59+
if i+len(word) <=len(s) && s[i:i+len(word)] == word {
60+
dp[i+len(word)] =true
61+
}
62+
}
63+
}
64+
}
65+
return dp[len(s)]
66+
}
67+
```
68+
69+
###递归
70+
>思路2
71+
```go
72+
package main
73+
74+
funcwordBreak3(sstring,wordDict []string)bool {
75+
ans:=make(map[string]bool)
76+
returnhelper(s, wordDict, ans)
77+
}
78+
79+
//s 每次比对的字符串
80+
//wordDict 目标字典列表
81+
// 匹配结果
82+
funchelper(sstring,wordDict []string,ansmap[string]bool)bool {
83+
//终止条件
84+
iflen(s) ==0 {
85+
returntrue
86+
}
87+
88+
ifres,ok:= ans[s]; ok {
89+
return res
90+
}
91+
92+
for_,word:=range wordDict {
93+
iflen(word) >len(s) || word != s[:len(word)] {
94+
continue
95+
}
96+
97+
ifhelper(s[len(word):], wordDict, ans) {
98+
ans[s] =true
99+
returntrue
100+
}
101+
102+
}
103+
ans[s] =false
104+
105+
returnfalse
106+
}
107+
108+
```
109+
110+
##结语
111+
112+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
113+
114+
[title]:https://leetcode.com/problems/word-break
115+
[me]:https://github.com/kylesliu/awesome-golang-leetcode

‎src/0139.Word-Break/Solution.go

Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
package Solution
2+
3+
//暴力遍历 比较 时间复杂度到 O(N3)
4+
funcwordBreak(sstring,wordDict []string)bool {
5+
dp:=make([]bool,len(s)+1)
6+
dp[0]=true
7+
8+
fori:=1;i<=len(s);i++ {
9+
forj:=0;j<=i-1;j++ {
10+
ifdp[j]==true {
11+
for_,word:=rangewordDict {
12+
ifs[j:i]==word {
13+
dp[i]=true
14+
break
15+
}
16+
}
17+
}
18+
19+
}
20+
}
21+
returndp[len(s)]
22+
}
23+
24+
//一次遍历时间复杂度 O(N2)
25+
funcwordBreak2(sstring,wordDict []string)bool {
26+
dp:=make([]bool,len(s)+1)
27+
dp[0]=true
28+
29+
fori:=0;i<len(dp);i++ {
30+
ifdp[i] {
31+
for_,word:=rangewordDict {
32+
//巧妙的运用 i + word len 避免2层循环
33+
ifi+len(word)<=len(s)&&s[i:i+len(word)]==word {
34+
dp[i+len(word)]=true
35+
}
36+
}
37+
}
38+
}
39+
returndp[len(s)]
40+
}
41+
42+
//递归遍历
43+
funcwordBreak3(sstring,wordDict []string)bool {
44+
dict:=make(map[string]bool)
45+
returndfs(s,wordDict,dict)
46+
}
47+
48+
//s 每次比对的字符串
49+
//wordDict 目标字典列表
50+
// 匹配结果
51+
funcdfs(sstring,wordDict []string,dictmap[string]bool)bool {
52+
//终止条件
53+
iflen(s)==0 {
54+
returntrue
55+
}
56+
57+
ifres,ok:=dict[s];ok {
58+
returnres
59+
}
60+
61+
for_,word:=rangewordDict {
62+
iflen(word)>len(s)||word!=s[:len(word)] {
63+
continue
64+
}
65+
66+
ifdfs(s[len(word):],wordDict,dict) {
67+
dict[s]=true
68+
returntrue
69+
}
70+
71+
}
72+
dict[s]=false
73+
74+
returnfalse
75+
}

‎src/0139.Word-Break/Solution_test.go

Lines changed: 92 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,92 @@
1+
package Solution
2+
3+
import (
4+
"reflect"
5+
"strconv"
6+
"testing"
7+
)
8+
9+
funcTestSolution1(t*testing.T) {
10+
//测试用例
11+
cases:= []struct {
12+
namestring
13+
input1string
14+
input2 []string
15+
expectbool
16+
}{
17+
{"TestCase","leetcode", []string{"leet","code"},true},
18+
{"TestCase","applepenapple", []string{"apple","pen"},true},
19+
{"TestCase","catsandog", []string{"cats","dog","sand","and","cat"},false},
20+
}
21+
22+
//开始测试
23+
fori,c:=rangecases {
24+
t.Run(c.name+" "+strconv.Itoa(i),func(t*testing.T) {
25+
got:=wordBreak(c.input1,c.input2)
26+
if!reflect.DeepEqual(got,c.expect) {
27+
t.Fatalf("expected: %v, but got: %v, with input1: %v input2: %v",
28+
c.expect,got,c.input1,c.input2)
29+
}
30+
})
31+
}
32+
}
33+
34+
funcTestSolution2(t*testing.T) {
35+
//测试用例
36+
cases:= []struct {
37+
namestring
38+
input1string
39+
input2 []string
40+
expectbool
41+
}{
42+
{"TestCase","leetcode", []string{"leet","code"},true},
43+
{"TestCase","applepenapple", []string{"apple","pen"},true},
44+
{"TestCase","catsandog", []string{"cats","dog","sand","and","cat"},false},
45+
}
46+
47+
//开始测试
48+
fori,c:=rangecases {
49+
t.Run(c.name+" "+strconv.Itoa(i),func(t*testing.T) {
50+
got:=wordBreak2(c.input1,c.input2)
51+
if!reflect.DeepEqual(got,c.expect) {
52+
t.Fatalf("expected: %v, but got: %v, with input1: %v input2: %v",
53+
c.expect,got,c.input1,c.input2)
54+
}
55+
})
56+
}
57+
}
58+
59+
funcTestSolution3(t*testing.T) {
60+
//测试用例
61+
cases:= []struct {
62+
namestring
63+
input1string
64+
input2 []string
65+
expectbool
66+
}{
67+
{"TestCase","leetcode", []string{"leet","code"},true},
68+
{"TestCase","applepenapple", []string{"apple","pen"},true},
69+
{"TestCase","catsandog", []string{"cats","dog","sand","and","cat"},false},
70+
}
71+
72+
//开始测试
73+
fori,c:=rangecases {
74+
t.Run(c.name+" "+strconv.Itoa(i),func(t*testing.T) {
75+
got:=wordBreak3(c.input1,c.input2)
76+
if!reflect.DeepEqual(got,c.expect) {
77+
t.Fatalf("expected: %v, but got: %v, with input1: %v input2: %v",
78+
c.expect,got,c.input1,c.input2)
79+
}
80+
})
81+
}
82+
}
83+
84+
//压力测试
85+
funcBenchmarkSolution(b*testing.B) {
86+
87+
}
88+
89+
//使用案列
90+
funcExampleSolution() {
91+
92+
}

‎src/0140.Word-Break-II/README.md

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
#[140. Word Break II][title]
2+
3+
##Description
4+
5+
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. Return all such possible sentences.
6+
7+
Note:
8+
9+
The same word in the dictionary may be reused multiple times in the segmentation.
10+
You may assume the dictionary does not contain duplicate words.
11+
**Example 1:**
12+
13+
```
14+
Input:
15+
s = "catsanddog"
16+
wordDict = ["cat", "cats", "and", "sand", "dog"]
17+
Output:
18+
[
19+
"cats and dog",
20+
"cat sand dog"
21+
]
22+
```
23+
24+
**Example 2:**
25+
26+
```
27+
Input:
28+
s = "pineapplepenapple"
29+
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
30+
Output:
31+
[
32+
"pine apple pen apple",
33+
"pineapple pen apple",
34+
"pine applepen apple"
35+
]
36+
Explanation: Note that you are allowed to reuse a dictionary word.
37+
```
38+
39+
**Tags:** Math, String
40+
41+
##题意
42+
>求2数之和
43+
44+
##题解
45+
46+
###思路1
47+
>。。。。
48+
49+
```go
50+
51+
```
52+
53+
###思路2
54+
>思路2
55+
```go
56+
57+
```
58+
59+
##结语
60+
61+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
62+
63+
[title]:https://leetcode.com/problems/word-break-ii/
64+
[me]:https://github.com/kylesliu/awesome-golang-leetcode

‎src/0140.Word-Break-II/Solution.go

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
package Solution
2+
3+
funcwordBreak(sstring,wordDict []string) []string {
4+
returndfs(s,wordDict,map[string][]string{})
5+
}
6+
7+
funcdfs(sstring,wordDict []string,dictmap[string][]string) []string {
8+
ifres,ok:=dict[s];ok {
9+
returnres
10+
}
11+
iflen(s)==0 {
12+
return []string{""}
13+
}
14+
15+
varres []string
16+
17+
for_,word:=rangewordDict {
18+
iflen(word)<=len(s)&&word==s[:len(word)] {
19+
for_,str:=rangedfs(s[len(word):],wordDict,dict) {
20+
iflen(str)==0 {
21+
res=append(res,word)
22+
}else {
23+
res=append(res,word+" "+str)
24+
}
25+
}
26+
27+
}
28+
}
29+
dict[s]=res
30+
returnres
31+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp