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));
}
}
這道題目一開(kāi)始我的實(shí)現(xiàn)方式不是這樣的怖侦。順序反了篡悟，導(dǎo)致時(shí)間測(cè)試總是過(guò)不了谜叹。然后網(wǎng)上看了提示才寫(xiě)了出來(lái)。
好久沒(méi)刷題搬葬，感覺(jué)那種做題的感覺(jué)已經(jīng)消耗光了荷腊。沒(méi)事，慢慢來(lái)吧急凰。
這道題目第一感覺(jué)肯定是用HashMap停局。
但是，在以誰(shuí)為原型香府，放入hashmap中董栽，我卻犯了錯(cuò)誤。
我把 string s 作為原型放入哈希表中企孩。導(dǎo)致每次換一個(gè)起始位置時(shí)都要重構(gòu)哈希表锭碳。浪費(fèi)了大量的操作。我的做法相當(dāng)于是把s存起來(lái)勿璃。然后拿words來(lái)和s比較擒抛。
但反一反，會(huì)更加的簡(jiǎn)潔补疑。
也就是說(shuō)歧沪，我把words存在一個(gè)哈希表中，拿s去進(jìn)行比較莲组。這樣我的哈希表就不用每次都重構(gòu)了诊胞。因?yàn)閣ords是永恒不變的。
然后還有個(gè)小技巧锹杈，幫助words的哈希表永恒不變撵孤。
當(dāng)我的比較字符串是s時(shí)，按道理竭望，我會(huì)把拆成一塊塊邪码。然后對(duì)words的哈希表進(jìn)行移除操作。如果最后哈希表正好全部光了咬清，那么闭专，一定是對(duì)的。但是這樣就會(huì)改變words旧烧，和我以前的做法影钉，沒(méi)什么差別。那么如何不改變words呢粪滤？
新建一個(gè)哈希表斧拍，對(duì)s建立這個(gè)哈希表。然后如果某塊substring 在 words對(duì)應(yīng)的哈希表中沒(méi)有出現(xiàn)杖小，
或者在words對(duì)應(yīng)的哈希表中出現(xiàn)的次數(shù)更少肆汹，那么就是錯(cuò)的。
遍歷結(jié)束后再返回true予权。
基本思路就是這樣了昂勉。
感覺(jué)自己的思維還是很不對(duì)。而且以前的感覺(jué)也沒(méi)了∩ㄏ伲現(xiàn)在看到題目腦子會(huì)犯渾岗照。而且再怎么簡(jiǎn)單的題目，也很難一次做對(duì)笆环。這個(gè)要注意改正攒至。
**
總結(jié)： 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);
}
}
自己寫(xiě)了出來(lái)，但是一看時(shí)間測(cè)試不對(duì)躁劣，比較慢迫吐。后來(lái)查了答案，才知道還有一種更優(yōu)化的解法账忘，也是這道題木志膀，真正的考點(diǎn)，意義鳖擒。
sliding window
然后我重寫(xiě)了如下：
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;
}
}
這道題木的思想是溉浙，第一層循環(huán)，就遍歷蒋荚， [o, len)
然后每一個(gè)循環(huán)戳稽，都是以len為單位得跳。
比如我已經(jīng)檢測(cè)了 [start, j + len), 這一塊期升，
此時(shí)广鳍，如果發(fā)現(xiàn)
[j, j + len) 不存在于s中，直接清空哈希表cmp吓妆，counter = 0,然后讓start指向 j + len,
[start, j + len) 不可能是組成最終結(jié)果的其中一部分了赊时，因?yàn)橛衃j, j + len) 的存在。
如果存在于s中行拢，counter++
如果該字符串出現(xiàn)次數(shù)已經(jīng)大于words限定了祖秒。那么在[start, j + len) 中，一定存在一個(gè)多余出來(lái)的該字符串舟奠。在該字符串前的其他字符竭缝，不會(huì)是構(gòu)成最終結(jié)果的一部分。
于是開(kāi)始用sliding window沼瘫，一個(gè)窗口一個(gè)窗口的減抬纸，直到發(fā)現(xiàn)某個(gè)時(shí)刻，該字符串出現(xiàn)次數(shù)正常了耿戚，就退出循環(huán)湿故。
用sliding window 做真的是節(jié)約了資源阿趁。
參考網(wǎng)頁(yè)：
http://www.programcreek.com/2013/02/longest-substring-which-contains-2-unique-characters/
然后對(duì)應(yīng)的一道谷歌的衍生題木，很類(lèi)似坛猪。
http://www.programcreek.com/2013/02/longest-substring-which-contains-2-unique-characters/
看來(lái)這個(gè)思想還是很重要的脖阵。也是我今天第一次接觸。好好記住了墅茉！
Anyway, Good luck, Richardo!
