Skip to content

Instantly share code, notes, and snippets.

@wayetan
Last active October 16, 2019 18:55
Show Gist options
  • Save wayetan/9427934 to your computer and use it in GitHub Desktop.
Save wayetan/9427934 to your computer and use it in GitHub Desktop.
Substring with Concatenation of All Words
/**
* You are given a string, S, and a list of words, L, that are all of the same length.
* Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.
* For example, given:
* S: "barfoothefoobarman"
* L: ["foo", "bar"]
* You should return the indices: [0,9].
* (order does not matter).
*/
public class Solution {
public ArrayList<Integer> findSubstring(String S, String[] L) {
ArrayList<Integer> indices = new ArrayList<Integer>();
if (L.length == 0)
return indices;
// notice: all the same length
int total = L.length, wordLen = L[0].length();
// Store the words and frequences in a hash table for L array
HashMap<String, Integer> words = new HashMap<String, Integer>();
for (String s : L) {
if(words.containsKey(s))
words.put(s, words.get(s) + 1);
else
words.put(s, 1);
}
// find the concatenations
for (int i = 0; i <= S.length() - total * wordLen; i++) {
// check if it is a concatenation
HashMap<String, Integer> target = new HashMap<String, Integer>(words);
for (int j = i; j <= S.length() - wordLen && !target.isEmpty(); j += wordLen) {
String sub = S.substring(j, j + wordLen);
if(!target.containsKey(sub))
break;
else if (target.get(sub) > 1) {
// reduce the frequency
target.put(sub, target.get(sub) - 1);
} else {
// remove the word if only one left
target.remove(sub);
}
}
if (target.isEmpty()) {
indices.add(i);
}
}
return indices;
}
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> res = new ArrayList<Integer>();
if(words.length == 0) return res;
int count = words.length, wordLen = words[0].length();
HashMap<String, Integer> map = new HashMap<String, Integer>();
for(String word : words) {
map.put(word, map.getOrDefault(word, 0) + 1);
}
HashMap<String, Integer> found = new HashMap<String, Integer>();
for(int i = 0; i <= s.length() - count * wordLen; i++) {
found.clear();
for(int j = 0; j < count; j++) {
int k = i + j * wordLen;
String str = s.substring(k, k + wordLen);
if(!map.containsKey(str)) break;
found.put(str, found.getOrDefault(str, 0) + 1);
if(found.get(str) > map.get(str)) break;
if(j == count - 1) res.add(i);
}
}
return res;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment