Given a text T and a word W, find all occurrences of permutations of W in T. Example: W = abc; T = dacbeacfabc. W appears in T twice: at index 1 (acb) and at index 8 ( abc).
Came up with this solution:
public static List<Integer> find(String T, String W){
List<Integer> result = new ArrayList<>();
if(T == null || T.length() == 0 || W == null || W.length() == 0)
return result;
List<String> permutation = permutate(W);
for(String s:permutation){
int index = 0;
while(index != -1){
index = T.indexOf(s, index);
if(index != -1){
result.add(index);
index++;
}
}
}
return result;
}
public static List<String> permutate(String W){
List<String> result = new ArrayList<>();
boolean[] visited = new boolean[W.length()];
backtrack(W,result, visited, new StringBuilder());
return result;
}
public static void backtrack(String W,List<String> result,boolean[] visited, StringBuilder sb ){
if(sb.length() == W.length())
result.add(sb.toString());
else{
for(int i = 0; i < W.length(); i++){
if(visited[i])
continue;
visited[i] = true;
sb.append(W.charAt(i));
backtrack(W,result, visited, sb);
visited[i] = false;
sb.deleteCharAt(sb.length() - 1);
}
}
}
O(n! * m*k)but this is actually sliding window
https://leetcode.com/problems/find-all-anagrams-in-a-string/