Amazon | SDE-2 | First Round
Anonymous User
1504
AmazonInterview

Problem Statement :

Given word and dictionary of words, search the word in dictionary such that, more than one occurances can be skipped while matching.

Examples below :

example 1 :

word = "lleeetttcooodddee"
dictionary = ["letcode", "leettccf", "lleetcode", "leetcod"]

output : true

example 2 :

word = "lleeetttcooodddee"
dictionary = ["leettccf", "lleetcode", "leetcod"]

output : true

example 3 :

word = "lleeetttcooodddee"
dictionary = ["leettccf", "leetcod"]

output : false

Follow up : return the word matched from dictionary

I tried the problem using Backtracking and Trie Data structure for searching word in dictionary. Interviewer wants my to optimize the solution but i am unable to do that.

Any suggestion for optimization or DP approach?

here's my solution :

class Solution {

    public static void main(String[] args) {
        System.out.println();
        String word = "lleeetttcooodddee";
        String[] dicts = new String[]{"letcode", "leettccf", "lleetcode", "leeg"};
        int ans = search(word, dicts);
        System.out.println(ans!=-1);
    }

    public static int search(String word, String[] dicts) {
        Node head = new Node();
        for (int i = 0; i < dicts.length; i++) buildTrie(dicts, i, 0, head);
        return dfs(word, dicts, 0, head);
    }

    private static int dfs(String word, String[] dicts, int index, Node head) {

        if (head == null || head.nodes[word.charAt(index) - 'a'] == null) return -1;

        int i = index + 1;

        while (i < word.length() && word.charAt(i) == word.charAt(index)) i++;
        if (i == word.length() && head.nodes[word.charAt(index) - 'a'].word != -1) {
            return head.nodes[word.charAt(index) - 'a'].word;
        }


        int res = -1;
        i = index + 1;
        while (i < word.length()) {
            res = dfs(word, dicts, i, head.nodes[word.charAt(index) - 'a']);
            if (res != -1) return res;
            else if (word.charAt(i) != word.charAt(index)) return -1;
//            // skip all duplicates chars
            while (i < word.length() && word.charAt(i) == word.charAt(index)) i++;
        }
        return res;

    }

    private static void buildTrie(String[] dicts, int dictIndex, int index, Node head) {
        if (index >= dicts[dictIndex].length()) {
            head.word = dictIndex;
            return;
        }
        char c = dicts[dictIndex].charAt(index);
        if (head.nodes[c - 'a'] == null) head.nodes[c - 'a'] = new Node();
        buildTrie(dicts, dictIndex, index + 1, head.nodes[c - 'a']);
    }

    static class Node {
        int word;
        private Node[] nodes;

        Node() {
            this.nodes = new Node[26];
            this.word = -1;
        }
    }
}
Comments (8)