Microsoft Phone Interview
Anonymous User
740

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/

Comments (1)