30. Substring with Concatenation of All Words (Hard)
https://leetcode.com/problems/substring-with-concatenation-of-all-words/
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 1:
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.
Example 2:
Input:
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
Output: []
Solutions
class Solution {
// This problem should not be classified as hard.
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> ans = new LinkedList<>();
if (s == null || s.length() == 0 || words.length == 0) {
return ans;
}
// length of each word
int wordLen = words[0].length();
// length of the combination of all the words
int combLen = wordLen * words.length;
// Combination string should not be longer than given s
if (s.length() < combLen) {
return ans;
}
// Keep the word frequency in words
Map<String, Integer> wordsFreqMap = new HashMap<>();
// Initialization
for (int i = 0; i < words.length; i++) {
if (!wordsFreqMap.containsKey(words[i])) {
wordsFreqMap.put(words[i], 0);
}
wordsFreqMap.put(words[i], wordsFreqMap.get(words[i]) + 1);
}
for (int i = 0; i <= s.length() - combLen; i++) {
boolean matched = true;
// Keep the frequency of matched words in s
Map<String, Integer> matchedFreqMap = new HashMap<>();
String ss = s.substring(i, i + combLen);
for (int j = 0; j < words.length; j++) {
String sss = ss.substring(j * wordLen, (j + 1) * wordLen);
if (!matchedFreqMap.containsKey(sss)) {
matchedFreqMap.put(sss, 0);
}
matchedFreqMap.put(sss, matchedFreqMap.get(sss) + 1);
// if word sss does not exist in the dictionary or its frequency larger than required, we take it unmatched.
if (!wordsFreqMap.containsKey(sss) || matchedFreqMap.get(sss) > wordsFreqMap.get(sss)) {
matched = false;
break;
}
}
if (matched) {
ans.add(i);
}
}
return ans;
}
}