030 Substring with Concatenation of All Words[H]

1 題目描述

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.

難度：Hard

2 題目樣例

For example, given:

s: "barfoothefoobarman" words: ["foo", "bar"]

You should return the indices: [0,9].

3 題意分析

弄懂這題目的意思花了我五分鐘。我們來針對題目中給出的樣例進行說明。

函數的參數是一個字元串，以及一個字元數組。在樣例中，字元串是"barfoothefoobarman"，字元數組是["foo", "bar"]。要求返回的是以字元數組中單詞串聯起來的子串的起始位置。這裡字元數組中單詞的順序是可以調換的。

比如在字元串"barfoothefoobarman"中，barfoo是給定字元數組中單詞的串聯，那麼返回的第一個數字就是0。而foobar也是串聯之一，那麼返回的第二個數字就是9。

4 思路分析

小弟不才......自己只能想出最簡單，時間複雜度最高的那種演算法。OTZ

這種演算法說起來是最簡單的，把給出的字元串遍歷一遍，取出每一個有可能包含字元串數組中包含單詞的部分（也就是按照單詞的長度對字元串進行切分），最後再用map進行判斷就可以了。但這種方法由於需要遍歷，複雜度是 （這裡我們假設n是字元串的長度，m是字元串數組中單詞的長度）。

代碼實現如下：

class Solution { public: vector<int> findSubstring(string S, vector<string> &L) { map<string, int> words; map<string, int> curWords; vector<int> ret; int slen = S.length(); if (!slen || L.empty()) return ret; int llen = L.size(), wlen = L[0].length(); for (auto &i : L) ++words[i]; for (int i = 0; i + llen * wlen <= slen; i++) { curWords.clear(); int j = 0; for (j = 0; j < llen; j++) { string tmp = S.substr(i + j * wlen, wlen); if (words.find(tmp) == words.end()) break; ++curWords[tmp]; if (curWords[tmp] > words[tmp]) break; } if (j == llen) ret.push_back(i); } return ret; } };

討論區里還有一種神乎其神的方法，這種方法不按照一個個字母對字元串進行分割，而是直接按照詞進行分割，因此在 的時間複雜度內就可以解決問題。

如果我們細心，會發現這個題目在提交的時候有個標籤——

看起來似乎...這個題目是標籤題目的簡化版本？

抱著試一試的態度，我找到了這樣一位神犇的代碼。

因為L中所有單詞的長度是一樣的，這樣根據wordLen，可以將S分為wordLen組，實際意思是這樣的。

以題目中barfoothefoobarman舉例，L中單詞長度為3，可以分為

bar|foo|the|foo|bar|man

ba|rfo|oth|efo|oba|rma|n

b|arf|oot|hef|oob|arm|an

這樣，針對每個分組，可以利用最小滑動窗口的思想，快速的判斷是否包含需要的字元串。

直觀上來看，1和2好像都是需要從每個字元開始搜索，實際上，2利用兩個指針去在S中尋找滿足條件的字元串，並且是每次+wordLen，而且不會重複的去統計，節省了很多時間。

粘貼代碼如下：

public class Solution { public ArrayList<Integer> findSubstring(String S, String[] L) { ArrayList<Integer> list = new ArrayList<Integer>(); int len = L.length; if (len == 0) { return list; } int wordLen = L[0].length(); Map<String, Integer> wordsMap = new HashMap<String, Integer>(); for (int i = 0; i < len; i++) { int num = 1; if (wordsMap.get(L[i]) != null) { num += wordsMap.get(L[i]); } wordsMap.put(L[i], num); } int slen = S.length(); int max = slen - wordLen + 1; for (int i = 0; i < wordLen; i++) { Map<String, Integer> numMap = new HashMap<String, Integer>(); int count = 0; int start = i; for (int end = start; end < max; end += wordLen) { String tempStr = S.substring(end, end + wordLen); if (!wordsMap.containsKey(tempStr)) { numMap.clear(); count = 0; start = end + wordLen; continue; } int num = 1; if (numMap.containsKey(tempStr)) { num += numMap.get(tempStr); } numMap.put(tempStr, num); if (num <= wordsMap.get(tempStr)) { count++; } else { while (numMap.get(tempStr) > wordsMap.get(tempStr)) { tempStr = S.substring(start, start + wordLen); numMap.put(tempStr, numMap.get(tempStr) - 1); if (numMap.get(tempStr) < wordsMap.get(tempStr)) { count--; } start += wordLen; } } if (count == len) { list.add(start); tempStr = S.substring(start, start + wordLen); numMap.put(tempStr, numMap.get(tempStr) - 1); count--; start += wordLen; } } } return list; } }

5 後記

在頭暈眼花中寫完這篇題解...可能存在某些胡言亂語之處，望各位指出並海涵。