Trie

Updated: 2021-12-15

Use the shorest unique prefix to represent each word in the array input: ["zebra", "dog", "duck",”dot”] output: {zebra: z, dog: dog, duck: du, dot:dot}

[zebra, dog, duck, dove]
{zebra:z, dog: dog, duck: du, dove: dov}

If it is just a prefix, not the full word, return empty string.

[bearcat, bear]
{bearcat: bearc, bear: ""}

{ab,abb,abbb}
{abbb:abbb;abb:"";ab:""}

Answer: use a trie(note that a trie is also called a prefix tree), for every char in the word increase the count of the corresponding node by one. Then for every word, find the first node that has the count of value 1.

class PrefixTreeNode{
public:
    PrefixTreeNode(int c){
        count=c;
        for(int i=0;i<26;i++)
            children[i]=NULL;
    }
    int count;
    PrefixTreeNode*children[26];
};

class ShortestUniquePrefixTree{
public:
    PrefixTreeNode*root;
    ShortestUniquePrefixTree(){
        root=new PrefixTreeNode(0);
    }
    void insert(string word){
        PrefixTreeNode*tmp=root;
        for(int i=0;i < word.length(); i++){
            if(tmp->children[word[i]-'a']!=NULL)

                tmp->children[word[i]-'a']->count++;
            else
                tmp->children[word[i]-'a']=new PrefixTreeNode(1);
            tmp=tmp->children[word[i]-'a'];
        }
    }
    string getShortestUniquePrefix(string word){
        PrefixTreeNode*tmp=root;
        for(int i=0;i<word.length();i++){
            if(tmp->children[word[i]-'a']==NULL) return "";
            else if(tmp->children[word[i]-'a']->count==1)
                return word.substr(0,i+1);
            else
                tmp=tmp->children[word[i]-'a'];
        }
        //if(tmp->count>1)
        return "";
    }
};

https://leetcode.com/discuss/oj/repeated-dna-sequences https://leetcode.com/discuss/25147/c-useing-trie http://www.programcreek.com/2012/12/leetcode-solution-word-break/ http://www.cnblogs.com/lautsie/p/3371354.html

word break

simple java solution using hashset and 4-based int

public List<String> findRepeatedDnaSequences(String s) {
    List<String> ans = new ArrayList<>();
    int len = s.length();
    HashSet<Integer> set = new HashSet<>();
    HashSet<Integer> res = new HashSet<>();
    for (int i = 10; i<= len; ++i){
        String sub = s.substring(i-10,i);
        int n = convert(sub);
        if (!res.contains(n)){
            if (!set.contains(n))
                set.add(n);
            else{
                ans.add(sub);
                res.add(n);
            }
        }
    }
    return ans;
}

public static int convert (String sub){
    int res = 0;
    HashMap<Character, Integer> dict = new HashMap<>();
    dict.put('A',0); dict.put('C',1);
    dict.put('G',2); dict.put('T',3);
    for (int i = 0; i< 10; ++i ){
        res+=dict.get(sub.charAt(i));
        res*=4;
    }
    return res;
}



Trie trie = new Trie();
for (String word : dict) {
    trie.add(word);
}

class Trie {
TrieNode root;

public void add(String word) {
root.add(word);
}
}

class TrieNode {

    char val;
    Set<TrieNode> children;

    TrieNode(char val) {
        this.val = val;
        this.children = new ArrayList<TrieNode>();
    }

    public void add(String word) {
        char v = word.charAt(0);
        if (children.contains(v)) {

        }
    }
}

/* IP: 6 bit integers

Route Table: "" -> 1 100 -> 2 10000 -> 10 1101 -> 3 011 -> 4

Ip Address: 100100 -> 2 011010 -> 4 000000 -> 1 100000 -> 10

*/

trie

public class Router {
// internal structure here

    private Trie trie = null;


    public void insert(boolean[] prefix, int port) {
        if (trie == null) {
            trie = new Trie();
        }
        trie.insert(prefix, port);

    }

    public int find(boolean[] ip) {


        TrieNode root = trie.getRoot();





        int rootPort = trie.getRoot().port;
        if (rootPort != -1) {
            return )
        }
    }

    class Trie {

        private TrieNode root;

        public Trie() {
            root = new TrieNode();
        }

        public void insert(boolean[] prefix, int port) {
            root.insert(prefix, port);
        }

        public int find(boolean[] ip) {
            root.find(ip);
        }

        public TrieNode getRoot() {
            return root;
        }
    }

    class TrieNode {

        //boolean value;
        TrieNode left = null;
        TrieNode right = null;
        int port = -1;


        public void insert(boolean[] input, int port) {
            if (input.length == 0) {
                this.port = port;
                return;
            }

            if (input[0]) {
                if (right == null) {
                    right = new TrieNode();
                }
                right.insert(input.subarray(1));


            } else {
                if (left == null) {
                    left = new TrieNode();
                }
                left.insert(input.subarray(1));
            }

        }

        /*
        100 -> 2

        -1
        \
        -1
        /
        -1
        /
        2

        11

        */
        public int find(boolean[] ip) {
            if (this.left == null && this.right == null) {
                return this.port;
            }

            if (ip[0]) {
                if (this.right == null) {
                    return this.port;
                } else {
                    right.find(input.subarray(1));
                }
            } else {
                if (this.left == null) {
                    return this.port;
                } else {
                    left.find(input.subarray(1));
                }
            }
        }
    }