# C++ solution: Bit Compression + Trie + BFS

• 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}

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;
}
}
}
}