You are given a string s and an array of strings words. All the strings of words are of the same length. A concatenated substring in s is a substring that contains all the strings of any permutation of words concatenated.
For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated substring because it is not the concatenation of any permutation of words.Return __the starting indices of all the concatenated substrings in __s. You can return the answer in **any order**.
Example 1: Input: s = “barfoothefoobarman”, words = [“foo”,“bar”] Output: [0,9] Explanation: Since words.length == 2 and words[i].length == 3, the concatenated substring has to be of length 6. The substring starting at 0 is “barfoo”. It is the concatenation of [“bar”,“foo”] which is a permutation of words. The substring starting at 9 is “foobar”. It is the concatenation of [“foo”,“bar”] which is a permutation of words. The output order does not matter. Returning [9,0] is fine too. Example 2: Input: s = “wordgoodgoodgoodbestword”, words = [“word”,“good”,“best”,“word”] Output: [] Explanation: Since words.length == 4 and words[i].length == 4, the concatenated substring has to be of length 16. There is no substring of length 16 in s that is equal to the concatenation of any permutation of words. We return an empty array. Example 3: Input: s = “barfoofoobarthefoobarman”, words = [“bar”,“foo”,“the”] Output: [6,9,12] Explanation: Since words.length == 3 and words[i].length == 3, the concatenated substring has to be of length 9. The substring starting at 6 is “foobarthe”. It is the concatenation of [“foo”,“bar”,“the”] which is a permutation of words. The substring starting at 9 is “barthefoo”. It is the concatenation of [“bar”,“the”,“foo”] which is a permutation of words. The substring starting at 12 is “thefoobar”. It is the concatenation of [“the”,“foo”,“bar”] which is a permutation of words.
Constraints:
1 <= s.length <= 104
1 <= words.length <= 5000
1 <= words[i].length <= 30
s and words[i] consist of lowercase English letters.
- code
class Solution {
private HashMap<String, Integer> wordCount = new HashMap<String, Integer>();
private int n;
private int wordLength;
private int substringSize;
private int k;
private void slidingWindow(int left, String s, List<Integer> answer) {
HashMap<String, Integer> wordsFound = new HashMap<>();
int wordsUsed = 0;
boolean excessWord = false;
// Do the same iteration pattern as the previous approach - iterate
// word_length at a time, and at each iteration we focus on one word
for (int right = left; right <= n - wordLength; right += wordLength) {
String sub = s.substring(right, right + wordLength);
if (!wordCount.containsKey(sub)) {
// Mismatched word - reset the window
wordsFound.clear();
wordsUsed = 0;
excessWord = false;
left = right + wordLength;
} else {
// If we reached max window size or have an excess word
while (right - left == substringSize || excessWord) {
String leftmostWord = s.substring(left, left + wordLength);
left += wordLength;
wordsFound.put(leftmostWord, wordsFound.get(leftmostWord) - 1);
if (wordsFound.get(leftmostWord) >= wordCount.get(leftmostWord)) {
// This word was an excess word
excessWord = false;
} else {
// Otherwise we actually needed it
wordsUsed--;
}
}
// Keep track of how many times this word occurs in the window
wordsFound.put(sub, wordsFound.getOrDefault(sub, 0) + 1);
if (wordsFound.get(sub) <= wordCount.get(sub)) {
wordsUsed++;
} else {
// Found too many instances already
excessWord = true;
}
if (wordsUsed == k && !excessWord) {
// Found a valid substring
answer.add(left);
}
}
}
}
public List<Integer> findSubstring(String s, String[] words) {
n = s.length();
k = words.length;
wordLength = words[0].length();
substringSize = wordLength * k;
for (String word : words) {
wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
}
List<Integer> answer = new ArrayList<>();
for (int i = 0; i < wordLength; i++) {
slidingWindow(i, s, answer);
}
return answer;
}
}
- code
class Solution {
private HashMap<String, Integer> wordCount = new HashMap<String, Integer>();
private int wordLength;
private int substringSize;
private int k;
private boolean check(int i, String s) {
// Copy the original dictionary to use for this index
HashMap<String, Integer> remaining = new HashMap<>(wordCount);
int wordsUsed = 0;
// Each iteration will check for a match in words
for (int j = i; j < i + substringSize; j += wordLength) {
String sub = s.substring(j, j + wordLength);
if (remaining.getOrDefault(sub, 0) != 0) {
remaining.put(sub, remaining.get(sub) - 1);
wordsUsed++;
} else {
break;
}
}
return wordsUsed == k;
}
public List<Integer> findSubstring(String s, String[] words) {
int n = s.length();
k = words.length;
wordLength = words[0].length();
substringSize = wordLength * k;
for (String word : words) {
wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
}
List<Integer> answer = new ArrayList<>();
for (int i = 0; i < n - substringSize + 1; i++) {
if (check(i, s)) {
answer.add(i);
}
}
return answer;
}
}
- code
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
int subLen = words[0].length() * words.length;
List<Integer> res = new ArrayList<>();
for (int i = 0; i < s.length() - subLen + 1; i++){
if (match(s.substring(i, i + subLen), new LinkedList<String>(Arrays.asList(words)))) res.add(i);
}
return res;
}
public boolean match(String s, List<String> words){
int count = words.size();
int wordLen = words.get(0).length();
for (int i = 0; i < count; i++){
String word = s.substring(i * wordLen, (i+1) * wordLen);
if (!words.contains(word)){
return false;
}else{
words.remove(word);
}
}
return words.size() == 0;
}
}