0030. Substring with Concatenation of All Words
https://leetcode.com/problems/substring-with-concatenation-of-all-words
Description
You are given a string s
and an array of strings words
of the same length. Return all starting indices of substring(s) in s
that is a concatenation of each word in words
exactly once, in any order, and without any intervening characters.
You can return the answer in any order.
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:** []
Example 3:
**Input:** s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
**Output:** [6,9,12]
Constraints:
1 <= s.length <= 104
s
consists of lower-case English letters.1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i]
consists of lower-case English letters.
ac1: 2 maps
time O(n k m), k is word count, m is word length space O(2k), k is word count
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> res = new ArrayList<Integer>();
// edge cases
if (s == null || words.length == 0 || s.length() < words[0].length()) return res;
// walk words, record word and count in map
int sl = s.length(), wl = words[0].length(), wcnt = words.length;
Map<String, Integer> map = new HashMap<String, Integer>();
for (String str : words) {
map.put(str, map.containsKey(str) ? map.get(str) + 1 : 1);
}
// walk string
for (int i = 0; i <= sl - wl * wcnt; i++) {
Map<String, Integer> seen = new HashMap<String, Integer>();
int j = i;
int k = wcnt;
while (k > 0) {
String w = s.substring(j, j + wl);
int seencnt = seen.getOrDefault(w, 0);
if (!map.containsKey(w) || seencnt >= map.get(w)) break;
seen.put(w, seencnt + 1);
k--;
j += wl;
}
if (k == 0) res.add(i); // this window has all words
}
// result
return res;
}
}
/*
1. walk words, record word and count in map
2. walk string:
copy a map, check whether window meet the requirement
*/
Last updated
Was this helpful?