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.
Example：
Input:
s = "barfoothefoobarman",
words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.
Input:
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
Output: []
解釋下題目：
這題目我看了半天才看懂！就是給定一個字符串s，還有若干個單詞的數(shù)組，每個單詞都是相同的長度，然后它們有個全排列，找出這個全排列中的任何一種可能在字符串s中出現(xiàn)的位置。就是如果我的單詞數(shù)組是["a","b","c"]，那么如果s中有abc,acb,bca,bac,cab,cba這六種可能中的任何一種符合，都要輸出。（PS：肯定不能全排列的）
1. 利用hashmap
實際耗時：225ms
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> res = new ArrayList<>();
//有多少單詞
int numOfWord = words.length;
if (numOfWord == 0) {
return res;
}
//每個單詞的長度 #題中說了每個單詞長度一樣
int wordLen = words[0].length();
//把所有單詞放進map1里面
Map<String, Integer> map1 = stringToMap(words, numOfWord);
for (int i = 0; i < s.length() - wordLen * numOfWord + 1; i++) {
Map<String, Integer> map2 = getMap(i, wordLen, numOfWord, s);
if (compareMap(map1, map2)) {
res.add(i);
}
}
return res;
}
//用所給的字符串，指定開始，并且指定每個單詞的長度，來構(gòu)造map
private Map<String, Integer> getMap(int start, int wordLen, int numOfWord, String s) {
String words[] = new String[numOfWord];
int j = 0;
for (int i = start; i < start + numOfWord * wordLen; i = i + wordLen) {
words[j] = s.substring(i, i + wordLen);
j++;
}
return stringToMap(words, numOfWord);
}
private Map<String, Integer> stringToMap(String words[], int numOfWord) {
Map<String, Integer> map = new HashMap<>();
for (int i = 0; i < numOfWord; i++) {
if (map.containsKey(words[i])) {
int count = map.get(words[i]);
count++;
map.put(words[i], count);
} else {
map.put(words[i], 1);
}
}
return map;
}
private boolean compareMap(Map<String, Integer> m1, Map<String, Integer> m2) {
Iterator<Map.Entry<String, Integer>> iter1 = m1.entrySet().iterator();
while (iter1.hasNext()) {
Map.Entry<String, Integer> entry1 = iter1.next();
int m1value = entry1.getValue() == null ? -1 : entry1.getValue();
int m2value = m2.get(entry1.getKey()) == null ? -2 : m2.get(entry1.getKey());
if (m1value != m2value) {
return false;
}
}
return true;
}
??思路是這樣的，全排列是絕對不可取的！那就用hashmap來存唄，上面的abc就可以存成{'a':1,'b':1,'c':1}，然后去比較兩個hashmap是否相同。這篇文章寫得更詳細，而且還有優(yōu)化。
