s******b
发帖数: 185 | 1 Substring with Concatenation of All Words
这个题，我做了多少次了，今晚看到，还是忘了思路。
不知道各位怎么样？ | w********o
发帖数: 33 | | y**********u
发帖数: 2839 | | w*******o
发帖数: 113 | 4 叔我来啦！
这道题就是说你先查一下words里每个单词的个数。注意每个单词都是等长的。
然后遍历字符串 像拿一根格尺，挨个比量一下，就可以了。
比如说：从 "barfoothefoobarman" 里找 ["foo", "bar"] 的链接
你先查一下，得到["foo": 1个, “bar” 1个]
然后遍历字符串
"barfoothefoobarman"
i
j
从i开始 截取3个字符是bar 然后你就 只需要再找["foo" 1个]
"barfoothefoobarman"
i
j
从j开始 截取3个是foo 然后就都找全了，可以把 i 放入结果里。
然后以每个i为开头的时候，都需要一个新的查数的表。
代码如下：
class Solution {
public List findSubstring(String s, String[] words) {
List res = new ArrayList<>();
int n = words.length, len = words[0].length();
Map map = new HashMap<>();
for (String w : words) map.put(w, map.getOrDefault(w, 0) + 1);
for (int i = 0; i <= s.length() - len * n; i++) {
Map m = new HashMap<>(map);
for (int j = 0; j < n; j++) {
String str = s.substring(i + j * len, i + j * len + len);
if (!m.containsKey(str)) break;
else {
m.put(str, m.get(str) - 1);
if (m.get(str) == 0) m.remove(str);
if (m.isEmpty()) res.add(i);
}
}
}
return res;
}
} | l********r
发帖数: 221 | 5 就是用sliding window的思路, 就不难了 | v******s
发帖数: 144 | 6 这是anagram的变种
外层循环找字典里任意字的开始位置，step size 1
内层循环和Anagram完全一样 step size n |
|
