30 Substring with Concatenation of All Words 串聯(lián)所有單詞的子串
Description:
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:
Example 1:
Input:
s = "barfoothefoobarman",
words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.
Example 2:
Input:
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
Output: []
題目描述:
給定一個字符串 s 和一些長度相同的單詞 words课兄。找出 s 中恰好可以由 words 中所有單詞串聯(lián)形成的子串的起始位置恕沫。
注意子串要與 words 中的單詞完全匹配，中間不能有其他字符量愧，但不需要考慮 words 中單詞串聯(lián)的順序佑附。
示例 :
示例 1：
輸入：
s = "barfoothefoobarman",
words = ["foo","bar"]
輸出：[0,9]
解釋：
從索引 0 和 9 開始的子串分別是 "barfoo" 和 "foobar" 。
輸出的順序不重要, [9,0] 也是有效答案。
示例 2：
輸入：
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
輸出：[]
思路:
- 對 words進(jìn)行排序, 遍歷字符串 s, 找出 words中的長度的字符串并排序再與排序后的 words的拼接結(jié)果比較, 相同就加入結(jié)果中
時間復(fù)雜度O(nmlgm), 空間復(fù)雜度O(m), 其中 n表示 s的長度, m表示 words拼接之后的長度 - 對于 方法1, 可以用哈希表存放 words并比較, 可以減少排序帶來的時間
時間復(fù)雜度O(nm), 空間復(fù)雜度O(m) - 滑動窗口
時間復(fù)雜度O(n), 空間復(fù)雜度O(m)
代碼:
C++:
class Solution
{
public:
vector<int> findSubstring(string s, vector<string>& words)
{
vector<int> result;
if (s.size() == 0 or words.size() == 0) return result;
unordered_map<string, int> m;
int word_size = words[0].size(), words_size = words.size(), s_size = s.size();
for (auto word : words) ++m[word];
for (int i = 0; i < word_size; i++)
{
int left = i, right = i, count = 0;
unordered_map<string, int> temp;
while (right + word_size <= s_size)
{
string word = s.substr(right, word_size);
right += word_size;
if (m.find(word) == m.end())
{
count = 0;
left = right;
temp.clear();
}
else
{
++temp[word];
++count;
while (temp[word] > m[word])
{
string test = s.substr(left, word_size);
--count;
--temp[test];
left += word_size;
}
if (count == words_size) result.push_back(left);
}
}
}
return result;
}
};
Java:
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> result = new ArrayList<>();
if (s.length() == 0 || words.length == 0) return result;
HashMap<String, Integer> map = new HashMap<>();
int word_size = words[0].length(), words_size = words.length, s_size = s.length();
for (String word : words) map.put(word, map.getOrDefault(word, 0) + 1);
for (int i = 0; i < word_size; i++) {
int left = i, right = i, count = 0;
HashMap<String, Integer> temp = new HashMap<>();
while (right + word_size <= s_size) {
String word = s.substring(right, right + word_size);
right += word_size;
if (!map.containsKey(word)) {
count = 0;
left = right;
temp.clear();
} else {
temp.put(word, temp.getOrDefault(word, 0) + 1);
count++;
while (temp.getOrDefault(word, 0) > map.getOrDefault(word, 0)) {
String test = s.substring(left, left + word_size);
count--;
temp.put(test, temp.getOrDefault(test, 0) - 1);
left += word_size;
}
if (count == words_size) result.add(left);
}
}
}
return result;
}
}
Python:
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
if not words or len(s) < len(words[0]) * len(words):
return []
result, wide, num, n, total = list(), len(words[0]), len(words), len(s), len(words[0]) * len(words)
words.sort()
for i in range(n + 1 - total):
l = [s[j : j + wide] for j in range(i, i + total, wide)]
l.sort()
if l == words:
result.append(i)
return result
