My code:
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
public class Solution {
public List<Integer> findSubstring(String s, String[] words) {
ArrayList<Integer> ret = new ArrayList<Integer>();
if (s == null || s.length() == 0 || words == null || words.length == 0)
return ret;
HashMap<String, Integer> check = new HashMap<String, Integer>();
int unitLen = words[0].length();
for (int i = 0; i < words.length; i++) {
if (!check.containsKey(words[i])) {
check.put(words[i], 1);
}
else {
int times = check.get(words[i]);
check.put(words[i], times + 1);
}
}
for (int i = 0; i <= s.length() - unitLen * words.length; i++) {
if (helper(i, words, check, s.substring(i, i + unitLen * words.length)))
ret.add(i);
}
return ret;
}
private boolean helper(int begin, String[] words, HashMap<String, Integer> check, String s) {
HashMap<String, Integer> cmp = new HashMap<String, Integer>();
int unitLen = words[0].length();
for (int i = 0; i < words.length; i++) {
String tmp = s.substring(unitLen * i, unitLen * (i + 1));
if (!cmp.containsKey(tmp)) {
cmp.put(tmp, 1);
}
else {
int times = cmp.get(tmp);
cmp.put(tmp, times + 1);
}
if (check.get(tmp) == null || cmp.get(tmp) > check.get(tmp))
return false;
}
return true;
}
public static void main(String[] args) {
Solution test = new Solution();
String s = "barfoothefoobarman";
String[] words = {"foo", "bar"};
System.out.println(test.findSubstring(s, words));
}
}
这道题目一开始我的实现方式不是这样的。顺序反了，导致时间测试总是过不了。然后网上看了提示才写了出来。
好久没刷题，感觉那种做题的感觉已经消耗光了。没事，慢慢来吧。
这道题目第一感觉肯定是用HashMap。
但是，在以谁为原型，放入hashmap中，我却犯了错误。
我把 string s 作为原型放入哈希表中。导致每次换一个起始位置时都要重构哈希表。浪费了大量的操作。我的做法相当于是把s存起来。然后拿words来和s比较。
但反一反，会更加的简洁。
也就是说，我把words存在一个哈希表中，拿s去进行比较。这样我的哈希表就不用每次都重构了。因为words是永恒不变的。
然后还有个小技巧，帮助words的哈希表永恒不变。
当我的比较字符串是s时，按道理，我会把拆成一块块。然后对words的哈希表进行移除操作。如果最后哈希表正好全部光了，那么，一定是对的。但是这样就会改变words，和我以前的做法，没什么差别。那么如何不改变words呢？
新建一个哈希表，对s建立这个哈希表。然后如果某块substring 在 words对应的哈希表中没有出现，
或者在words对应的哈希表中出现的次数更少，那么就是错的。
遍历结束后再返回true。
基本思路就是这样了。
感觉自己的思维还是很不对。而且以前的感觉也没了。现在看到题目脑子会犯浑。而且再怎么简单的题目，也很难一次做对。这个要注意改正。
**
总结： hash table
**
Anyway, Good luck, Richardo!
My code:
public class Solution {
public List<Integer> findSubstring(String s, String[] words) {
ArrayList<Integer> ret = new ArrayList<Integer>();
if (s == null || s.length() == 0 || words == null || words.length == 0)
return ret;
int len = words[0].length(); // record the length of one word
/** track the number of strings in words[] */
HashMap<String, Integer> tracker = new HashMap<String, Integer>();
for (int i = 0; i < words.length; i++) {
if (!tracker.containsKey(words[i])) {
tracker.put(words[i], 1);
}
else {
int times = tracker.get(words[i]);
tracker.put(words[i], times + 1);
}
}
int i = 0;
while (i <= s.length() - words.length * len) {
helper(i, tracker, words, s, ret);
i++;
}
return ret;
}
private void helper(int begin, HashMap<String, Integer> tracker, String[] words,
String s, ArrayList<Integer> ret) {
int len = words[0].length(); // record the length of one word
HashMap<String, Integer> copy = new HashMap<String, Integer>();
int i = begin;
while (i < begin + len * words.length) { // [begin, begin + len * words.length)
String curr = s.substring(i, i + len);
if (!tracker.containsKey(curr))
return;
else if (!copy.containsKey(curr)) {
copy.put(curr, 1);
}
else {
int times = copy.get(curr);
if (times + 1 > tracker.get(curr))
return;
else
copy.put(curr, times + 1);
}
i += len;
}
ret.add(begin);
}
}
自己写了出来，但是一看时间测试不对，比较慢。后来查了答案，才知道还有一种更优化的解法，也是这道题木，真正的考点，意义。
sliding window
然后我重写了如下：
My code:
public class Solution {
public List<Integer> findSubstring(String s, String[] words) {
ArrayList<Integer> ret = new ArrayList<Integer>();
if (s == null || s.length() == 0 || words == null || words.length == 0)
return ret;
int len = words[0].length(); // record the length of one word
/** track the number of strings in words[] */
HashMap<String, Integer> tracker = new HashMap<String, Integer>();
for (int i = 0; i < words.length; i++) {
if (!tracker.containsKey(words[i])) {
tracker.put(words[i], 1);
}
else {
int times = tracker.get(words[i]);
tracker.put(words[i], times + 1);
}
}
for (int i = 0; i < len; i++) {
int start = i;
HashMap<String, Integer> cmp = new HashMap<String, Integer>();
int counter = 0;
for (int j = i; j <= s.length() - len; j += len) { // window: [start, start len), keep moving left
String curr = s.substring(j, j + len);
if (tracker.containsKey(curr)) {
if (!cmp.containsKey(curr))
cmp.put(curr, 1);
else {
cmp.put(curr, cmp.get(curr) + 1);
}
counter++;
while (cmp.get(curr) > tracker.get(curr)) {
String pre = s.substring(start, start + len);
cmp.put(pre, cmp.get(pre) - 1);
start = start + len;
counter--;
}
if (counter == words.length) {
ret.add(start);
String pre = s.substring(start, start + len);
cmp.put(pre, cmp.get(pre) - 1);
counter--;
start += len;
}
}
else {
cmp.clear();
start = j + len;
counter = 0;
}
}
}
return ret;
}
}
这道题木的思想是，第一层循环，就遍历， [o, len)
然后每一个循环，都是以len为单位得跳。
比如我已经检测了 [start, j + len), 这一块，
此时，如果发现
[j, j + len) 不存在于s中，直接清空哈希表cmp，counter = 0,然后让start指向 j + len,
[start, j + len) 不可能是组成最终结果的其中一部分了，因为有[j, j + len) 的存在。
如果存在于s中，counter++
如果该字符串出现次数已经大于words限定了。那么在[start, j + len) 中，一定存在一个多余出来的该字符串。在该字符串前的其他字符，不会是构成最终结果的一部分。
于是开始用sliding window，一个窗口一个窗口的减，直到发现某个时刻，该字符串出现次数正常了，就退出循环。
用sliding window 做真的是节约了资源。
参考网页：
http://www.programcreek.com/2013/02/longest-substring-which-contains-2-unique-characters/
然后对应的一道谷歌的衍生题木，很类似。
http://www.programcreek.com/2013/02/longest-substring-which-contains-2-unique-characters/
看来这个思想还是很重要的。也是我今天第一次接触。好好记住了！
Anyway, Good luck, Richardo!
