C++ solution: Bit Compression + Trie + BFS


  • 0
    I

    This problem could be more general than it is. For example:

    • the string length may not need to be always 8
    • the character could be more than {A, G, C, T}

    So this article is for more general scenario.

    In this solution, I will use Trie to store word bank. The reason for using Trie is:

    • when word bank has large number of words, time searching in Trie is O(|W|), where |W| = length of string to be mutated.

    Here is the code:

    struct TrieNode {
        bool isWord, visited;
        TrieNode *child[26];
    
        TrieNode() : isWord(false), visited(false) {
            for(int i=0; i<26; i++){
                child[i] = 0;
            }
        }
    };
    
    struct Trie {
        TrieNode *root;
    
        Trie() {
            root = new TrieNode();
        }
    
        void insert(string s) {
            TrieNode *cur = root;
            int len = s.length();
            for(int i=0; i<len; i++){
                int idx = s[i]-'A';
                if(!cur->child[idx]) cur->child[idx] = new TrieNode();
                cur = cur->child[idx];
                if(i == len-1) cur->isWord = true;
            }
        }
    
        TrieNode* search(string s) {
            TrieNode *cur = root;
            int len = s.length();
            for(int i=0; i<len; i++){
                int idx = s[i]-'A';
                if(!cur->child[idx]){
                    return 0;
                }else{
                    cur = cur->child[idx];
                    if(i == len-1) return cur->isWord ? cur : 0;
                }
            }
            return 0;
        }
    };
    
    class Solution {
    public:
        int getIdx(char c) {
            switch (c) {
                case 'A': return 0;
                case 'G': return 1;
                case 'C': return 2;
                case 'T': return 3;
                default: return -1;
            }
        }
    
        long getBitSum(string s) {
            long num = 0;
            for(int i=0; i<s.length(); i++){
                num += getIdx(s[i]) * 1 << (2*i);
            }
            return num;
        }
    
        string genStrMutation(string curStr, int pos, int charIdx) {
            long curBitSum = getBitSum(curStr);
            long nextBitSum = curBitSum ^ charIdx << (pos * 2);
            char map[4] = {'A','G','C','T'};
            string s;
            int len = curStr.length();
            for(int i=0; i<len; i++){
                int idx = 3 & nextBitSum;
                s.insert(s.end(), map[idx]);
                nextBitSum >>= 2;
            }
            return s;
        }
    
        int minMutation(string start, string end, vector<string>& bank) {
            Trie bankTrie;
            for(int i=0; i<bank.size(); i++){
                bankTrie.insert(bank[i]);
            }
    
            queue<pair<string, int>> q;
            q.push(make_pair(start, 0));
    
            int totalStep = -1;
    
            while(q.size()){
                string curStr = q.front().first;
                int curStep = q.front().second;
                q.pop();
    
                if(curStr.compare(end) == 0){
                    totalStep = curStep;
                    break;
                }
    
                int len = curStr.length();
                for(int i=0; i<len; i++){
                    for(int j=0; j<4; j++){
                        string s = genStrMutation(curStr, i, j);
                        TrieNode *word = bankTrie.search(s);
                        if(word!=0 && !word->visited) {
                            q.push(make_pair(s, curStep+1));
                            word->visited = true;
                        }
                    }
                }
            }
    
            return totalStep;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.