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

Commit7100e36

Browse files
committed
add: 030
1 parent8a4378d commit7100e36

File tree

3 files changed

+166
-9
lines changed

3 files changed

+166
-9
lines changed

‎README.md

Lines changed: 11 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -92,15 +92,16 @@
9292

9393
##Hard
9494

95-
| #| Title| Tag|
96-
| :---| :---------------------------------| :---------------------------------------|
97-
| 4|[Median of Two Sorted Arrays][004]| Array, Binary Search, Divide and Conquer|
98-
| 10|[Regular Expression Matching][010]| String, Dynamic Programming, Backtracking|
99-
| 23|[Merge k Sorted Lists][023]| Linked List, Divide and Conquer, Heap|
100-
| 25|[Reverse Nodes in k-Group][025]| Linked List|
101-
| 44|[Wildcard Matching][044]| String, Dynamic Programming, Backtracking, Greedy|
102-
| 57|[Insert Interval][057]| Array, Sort|
103-
| 68|[Text Justification][068]| String|
95+
| #| Title| Tag|
96+
| :---| :---------------------------------------| :---------------------------------------|
97+
| 4|[Median of Two Sorted Arrays][004]| Array, Binary Search, Divide and Conquer|
98+
| 10|[Regular Expression Matching][010]| String, Dynamic Programming, Backtracking|
99+
| 23|[Merge k Sorted Lists][023]| Linked List, Divide and Conquer, Heap|
100+
| 25|[Reverse Nodes in k-Group][025]| Linked List|
101+
| 30|[Substring with Concatenation of All Words][030]| Hash Table, Two Pointers, String|
102+
| 44|[Wildcard Matching][044]| String, Dynamic Programming, Backtracking, Greedy|
103+
| 57|[Insert Interval][057]| Array, Sort|
104+
| 68|[Text Justification][068]| String|
104105

105106

106107

@@ -169,6 +170,7 @@
169170
[010]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/010/README.md
170171
[023]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/023/README.md
171172
[025]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/025/README.md
173+
[030]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/030/README.md
172174
[044]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/044/README.md
173175
[057]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/057/README.md
174176
[068]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/068/README.md

‎note/030/README.md

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
#[Substring with Concatenation of All Words][title]
2+
3+
##Description
4+
5+
You are given a string,**s**, and a list of words,**words**, that are all of the same length. Find all starting indices of substring(s) in**s** that is a concatenation of each word in**words** exactly once and without any intervening characters.
6+
7+
8+
For example, given:
9+
10+
**s**:`"barfoothefoobarman"`
11+
12+
**words**:`["foo", "bar"]`
13+
14+
You should return the indices:`[0,9]`.
15+
16+
(order does not matter).
17+
18+
**Tags:** Hash Table, Two Pointers, String
19+
20+
21+
##思路
22+
23+
题意是
24+
25+
```java
26+
27+
```
28+
29+
30+
##结语
31+
32+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-java-leetcode][ajl]
33+
34+
35+
36+
[title]:https://leetcode.com/problems/substring-with-concatenation-of-all-words
37+
[ajl]:https://github.com/Blankj/awesome-java-leetcode
Lines changed: 118 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,118 @@
1+
packagecom.blankj.hard._030;
2+
3+
importjava.util.ArrayList;
4+
importjava.util.Collections;
5+
importjava.util.HashMap;
6+
importjava.util.HashSet;
7+
importjava.util.List;
8+
importjava.util.Map;
9+
importjava.util.Set;
10+
11+
/**
12+
* <pre>
13+
* author: Blankj
14+
* blog : http://blankj.com
15+
* time : 2018/02/01
16+
* desc :
17+
* </pre>
18+
*/
19+
publicclassSolution {
20+
publicList<Integer>findSubstring(Strings,String[]words) {
21+
intwordsSize =words.length,wordLen =words[0].length(),end =s.length() -wordsSize *wordLen;
22+
if (end <0)returnCollections.emptyList();
23+
Map<String,Integer>countMap =newHashMap<>();
24+
for (Stringword :words) {
25+
countMap.put(word,countMap.getOrDefault(word,0) +1);
26+
}
27+
List<Integer>res =newArrayList<>();
28+
Set<Integer>ignores =newHashSet<>();
29+
for (inti =0;i <=end; ++i) {
30+
if (ignores.contains(i))continue;
31+
Map<String,Integer>findMap =newHashMap<>();
32+
intst =i,count =0;
33+
List<Integer>ignore =newArrayList<>();
34+
for (intj =0; ; ++j) {
35+
intcur =i +j *wordLen;
36+
if (cur +wordLen >s.length())break;
37+
Stringword =s.substring(cur,cur +wordLen);
38+
if (countMap.containsKey(word)) {
39+
findMap.put(word,findMap.getOrDefault(word,0) +1);
40+
++count;
41+
while (findMap.get(word) >countMap.get(word)) {
42+
ignore.add(st);
43+
Stringtmp =s.substring(st,st +=wordLen);
44+
findMap.put(tmp,findMap.get(tmp) -1);
45+
--count;
46+
}
47+
if (count ==wordsSize) {
48+
ignore.add(st);
49+
res.add(st);
50+
Stringtmp =s.substring(st,st +=wordLen);
51+
findMap.put(tmp,findMap.get(tmp) -1);
52+
--count;
53+
}
54+
}else {
55+
for (intk =i;k <=cur;k +=wordLen) {
56+
ignore.add(k);
57+
}
58+
break;
59+
}
60+
}
61+
ignores.addAll(ignore);
62+
}
63+
returnres;
64+
}
65+
66+
// public List<Integer> findSubstring(String S, String[] L) {
67+
// List<Integer> res = new LinkedList<>();
68+
// int N = S.length();
69+
// int M = L.length; // *** length
70+
// int wl = L[0].length();
71+
// Map<String, Integer> map = new HashMap<>(), curMap = new HashMap<>();
72+
// for (String s : L) {
73+
// if (map.containsKey(s)) map.put(s, map.get(s) + 1);
74+
// else map.put(s, 1);
75+
// }
76+
// String str = null, tmp = null;
77+
// for (int i = 0; i < wl; i++) {
78+
// int count = 0; // remark: reset count
79+
// int start = i;
80+
// for (int r = i; r + wl <= N; r += wl) {
81+
// str = S.substring(r, r + wl);
82+
// if (map.containsKey(str)) {
83+
// if (curMap.containsKey(str)) curMap.put(str, curMap.get(str) + 1);
84+
// else curMap.put(str, 1);
85+
//
86+
// if (curMap.get(str) <= map.get(str)) count++;
87+
// if (count == M) {
88+
// res.add(start);
89+
// tmp = S.substring(start, start + wl);
90+
// curMap.put(tmp, curMap.get(tmp) - 1);
91+
// start += wl;
92+
// count--;
93+
// }
94+
// while (curMap.get(str) > map.get(str)) {
95+
// tmp = S.substring(start, start + wl);
96+
// curMap.put(tmp, curMap.get(tmp) - 1);
97+
// start += wl;
98+
// if (curMap.get(tmp) < map.get(tmp)) count--;
99+
//
100+
// }
101+
// } else {
102+
// curMap.clear();
103+
// count = 0;
104+
// start = r + wl;
105+
// }
106+
// }
107+
// curMap.clear();
108+
// }
109+
// return res;
110+
// }
111+
112+
publicstaticvoidmain(String[]args) {
113+
Solutionsolution =newSolution();
114+
System.out.println(solution.findSubstring("wordgoodgoodgoodbestword",newString[]{"word","good","best","good"}));
115+
System.out.println(solution.findSubstring("barfoothefoobarman",newString[]{"foo","bar"}));
116+
System.out.println(solution.findSubstring("barfoofoobarthefoobarman",newString[]{"bar","foo","the"}));
117+
}
118+
}

0 commit comments

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