## Friday, October 21, 2016

### LeetCode 433 - Minimum Genetic Mutation

https://leetcode.com/problems/minimum-genetic-mutation/
A gene string can be represented by an 8-character long string, with choices from "A","C","G","T".
Suppose we need to investigate about a mutation (mutation from "start" to "end"), where ONE mutation is defined as ONE single character changed in the gene string.
For example, "AACCGGTT" -> "AACCGGTA" is 1 mutation.
Also, there is a given gene "bank", which records all the valid gene mutations. A gene must be in the bank to make it a valid gene string.

Now, given 3 things - start, end, bank, your task is to determine what is the minimum number of mutations needed to mutate from "start" to "end". If there is no such a mutation, return -1.

NOTE: 1. Starting point is assumed to be valid, so it might not be included in the bank. 2. If multiple mutations are needed, all mutations during in the sequence must be valid. For example,
bank: "AACCGGTA"
start: "AACCGGTT"
end: "AACCGGTA"
return: 1

bank: "AACCGGTA", "AACCGCTA", "AAACGGTA"
start: "AACCGGTT"
end: "AAACGGTA"
return: 2
bank: "AAAACCCC", "AAACCCCC", "AACCCCCC"
start: "AAAAACCC"
end: "AACCCCCC"
return: 3

https://discuss.leetcode.com/topic/63954/java-bfs-solution
Explain: Every time we find a mismatch letter then check if it is in the bank, if so, then we add it to the queue for bfs traverse. "#" is used to mark end of each level. time complexity should be o(length of bank)
``````    public int minMutation(String start, String end, String[] bank) {
Set<String> set=new HashSet<String>();//\\
char[] chars={'A','C','G','T'};

if(!set.contains(end))return -1;

while(!q.isEmpty()) {
Container con=q.remove();
char[] str=con.word.toCharArray();

for(int i=0;i<str.length;i++) {
char tmpChar=str[i];
for(char c:chars) {
if(c==str[i]) continue;
str[i]=c;
String tmpStr=new String(str);
if(tmpStr.equals(end))
return con.steps+1;
if(set.contains(tmpStr))

}
str[i]=tmpChar;
}
}
return -1;
}
class Container {
String word;
int steps;
public Container(String word,int steps) {
this.word=word;
this.steps=steps;
}
}``````
https://discuss.leetcode.com/topic/65780/java-solution-using-bfs
``````    public int minMutation(String start, String end, String[] bank) {
if(start.equals(end)) return 0;

Set<String> bankSet = new HashSet<>();

char[] charSet = new char[]{'A', 'C', 'G', 'T'};

int level = 0;
Set<String> visited = new HashSet<>();
queue.offer(start);

while(!queue.isEmpty()) {
int size = queue.size();
while(size-- > 0) {
String curr = queue.poll();
if(curr.equals(end)) return level;

char[] currArray = curr.toCharArray();
for(int i = 0; i < currArray.length; i++) {
char old = currArray[i];
for(char c: charSet) {
currArray[i] = c;
String next = new String(currArray);
if(!visited.contains(next) && bankSet.contains(next)) {
queue.offer(next);
}
}
currArray[i] = old;
}
}
level++;
}
return -1;
}``````

def minMutation(self, start, end, bank): """ :type start: str :type end: str :type bank: List[str] :rtype: int """ def toNumber(gene): table = {v : i for i, v in enumerate('ATGC')} return sum([table[g] * 1 << (2 * i) for i, g in enumerate(gene)]) bank = set(map(toNumber, bank)) start = toNumber(start) end = toNumber(end) queue = [(start, 0)] viset = set([start]) while queue: gene, step = queue.pop(0) if gene == end: return step for x in range(8): for y in range(4): next = gene ^ (y << (x * 2)) if next in bank and next not in viset: viset.add(next) queue.append((next, step + 1)) return -1

1. I tried running your java code on leet but it exceeds memory limitations....

2. The code based on bfs has a bug. After /* q.add(new Container(tmpStr,con.steps+1)); */ In the if condition only remove tmpstr from set so as not to add same str more than once in the queue.

1. public class Solution {
public int minMutation(String start, String end, String[] bank) {
Set hs=new HashSet();
char ch[]={'A','C','G','T'};
for(String s:bank)
if(!hs.contains(end))
return -1;
q.offer(new Node(start,0));
while(!q.isEmpty()){
Node n=q.poll();
char str[]=n.word.toCharArray();
for(int i=0;i<str.length;i++){
char temp=str[i];
for(char c:ch){
if(c==str[i])
continue;
str[i]=c;
String tempstr=new String(str);
if(tempstr.compareTo(end)==0)
return n.steps+1;
if(hs.contains(tempstr)){
q.offer(new Node(tempstr,n.steps+1));
hs.remove(tempstr);
}
}
str[i]=temp;
}
}
return -1;
}
}
class Node{
String word;
int steps;
Node(String word, int steps){
this.word=word;
this.steps=steps;
}
}

## Labels

GeeksforGeeks (1109) LeetCode (1095) Review (846) Algorithm (795) to-do (633) LeetCode - Review (574) Classic Algorithm (324) Dynamic Programming (294) Classic Interview (288) Google Interview (242) Tree (145) POJ (139) Difficult Algorithm (132) LeetCode - Phone (127) EPI (125) Bit Algorithms (120) Different Solutions (120) Lintcode (113) Smart Algorithm (109) Math (108) HackerRank (89) Binary Search (83) Binary Tree (82) Graph Algorithm (76) Greedy Algorithm (73) DFS (71) Stack (65) Interview Corner (61) List (58) BFS (54) Codility (54) ComProGuide (52) Trie (49) USACO (46) Interval (45) LeetCode Hard (42) ACM-ICPC (41) Data Structure (40) Knapsack (40) Jobdu (39) Matrix (39) String Algorithm (38) Union-Find (37) Backtracking (36) Codeforces (36) Must Known (36) Sort (35) Array (33) Segment Tree (33) Sliding Window (33) prismoskills (33) HDU (31) Priority Queue (31) Google Code Jam (30) Permutation (30) Puzzles (30) Array O(N) (29) Company-Airbnb (29) Company-Zenefits (28) Palindrome (28) to-do-must (28) Graph (27) Random (27) GeeksQuiz (25) Logic Thinking (25) Pre-Sort (25) Time Complexity (25) hihocoder (25) Queue (24) Company-Facebook (23) High Frequency (23) TopCoder (23) Algorithm Game (22) Bisection Method (22) Hash (22) DFS + Review (21) Two Pointers (21) Brain Teaser (20) CareerCup (20) LeetCode - DP (20) Merge Sort (20) O(N) (20) Follow Up (19) UVA (19) Ordered Stack (18) Probabilities (18) Company-Uber (17) Game Theory (17) Topological Sort (17) Codercareer (16) Heap (16) Shortest Path (16) String Search (16) Tree Traversal (16) itint5 (16) Difficult (15) Iterator (15) BST (14) KMP (14) LeetCode - DFS (14) Number (14) Number Theory (14) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Euclidean GCD (13) Majority (13) Reverse Thinking (13) mitbbs (13) Combination (12) Modify Tree (12) Reconstruct Tree (12) 尺取法 (12) AOJ (11) DFS+Backtracking (11) Graph DFS (11) LCA (11) Miscs (11) Princeton (11) Proof (11) Rolling Hash (11) Tree DP (11) X Sum (11) 挑战程序设计竞赛 (11) Bisection (10) Bucket Sort (10) Coin Change (10) DFS+Cache (10) HackerRank Easy (10) O(1) Space (10) SPOJ (10) Theory (10) TreeMap (10) Tutorialhorizon (10) Mathblog (9) Max-Min Flow (9) Prefix Sum (9) Quick Sort (9) Simulation (9) Stock (9) Use XOR (9) Book Notes (8) Bottom-Up (8) DFS+BFS (8) Linked List (8) Prime (8) Suffix Tree (8) Tech-Queries (8) 穷竭搜索 (8) Expression (7) Game Nim (7) Graph BFS (7) Hackerearth (7) Inversion (7) Quick Select (7) Radix Sort (7) TreeSet (7) n00tc0d3r (7) 蓝桥杯 (7) DFS+DP (6) DP - Tree (6) Dijkstra (6) Dutch Flag (6) How To (6) Manacher (6) One Pass (6) Pruning (6) Rabin-Karp (6) Sampling (6) Schedule (6) Stream (6) Suffix Array (6) Threaded (6) Xpost (6) reddit (6) AI (5) Big Data (5) Brute Force (5) Code Kata (5) Coding (5) Convex Hull (5) Crazyforcode (5) Cycle (5) Find Rule (5) Graph Cycle (5) Immutability (5) Java (5) Maze (5) Pre-Sum (5) Quadtrees (5) Quora (5) Subarray Sum (5) Sudoku (5) Sweep Line (5) Word Search (5) jiuzhang (5) 单调栈 (5) 树形DP (5) 1point3acres (4) Abbreviation (4) Anagram (4) Anagrams (4) Chess Game (4) Distributed (4) Flood fill (4) Histogram (4) MST (4) MinMax (4) N Queens (4) Probability (4) Programcreek (4) Subset Sum (4) Subsets (4) Symbol Table (4) Triangle (4) Water Jug (4) algnotes (4) fgdsb (4) to-do-2 (4) 最大化最小值 (4) A Star (3) B Tree (3) Coins (3) Dedup (3) Dequeue (3) Dropbox (3) Easy (3) Github (3) GoLang (3) Joseph (3) Jump Game (3) K (3) LogN (3) Minesweeper (3) NP Hard (3) O(N) Hard (3) Parser (3) Rectangle (3) Scala (3) SegmentFault (3) Shuffle (3) Skyline (3) Subtree (3) Trie + DFS (3) Word Ladder (3) bookkeeping (3) codebytes (3) Array Merge (2) BOJ (2) Bellman Ford (2) Bit Counting (2) Bit Mask (2) Bloom Filter (2) Clock (2) Codesays (2) DP - DFS (2) DP-3D Table (2) DP-Classical (2) DP-i-k-j (2) DP-树形 (2) Factor (2) GoHired (2) Graham Scan (2) Huffman Tree (2) Invariant (2) Islands (2) Lucene-Solr (2) Matrix Power (2) Median (2) Parentheses (2) Peak (2) Programming (2) Robot (2) Rosettacode (2) Search (2) SimHash (2) Summary (2) TV (2) Tile (2) Tree Sum (2) Word Break (2) Word Graph (2) Word Trie (2) 剑指Offer (2) 数位DP (2) 1-X (1) 51Nod (1) Akka (1) BACK (1) BK-Tree (1) BZOJ (1) Basic (1) Bayes (1) Big Integer (1) Big Number (1) Binary (1) Bipartite (1) BitMap (1) BitMap index (1) BitSet (1) BuildIt (1) C/C++ (1) CC Interview (1) Cache (1) Chinese (1) Clean Code (1) Cloest (1) Clone (1) Code Quality (1) Company-Epic (1) Company-Yelp (1) Concise (1) Concurrency (1) Custom Sort (1) DFS-Matrix (1) DP-Difficult (1) DP-Graph (1) DP-MaxMin (1) Database (1) Diagonal (1) Domino (1) Dr Dobb's (1) Duplicate (1) FST (1) Fraction (1) Funny (1) Game (1) Generation (1) GeoHash (1) Google APAC (1) Gray Code (1) HOJ (1) Hanoi (1) How Hash (1) How to Test (1) Improve It (1) In Place (1) Interview (1) Isomorphic (1) JDK8 (1) Knight (1) Kruskal (1) Kth Element (1) Linkedin (1) Local MinMax (1) Matrix BFS (1) Matrix Graph (1) Matrix+DP (1) MinHash (1) MinMax Heap (1) Monto Carlo (1) Multiple DFS (1) Next Element (1) PAT (1) Parenthesis (1) Partition (1) Path Finding (1) Persistent (1) Power Set (1) PreProcess (1) Python (1) RSA (1) Ranking (1) Rddles (1) ReHash (1) Realtime (1) Region (1) Resources (1) Robin (1) Selection (1) Similarity (1) Square (1) String DP (1) SubMatrix (1) Subsequence (1) TSP (1) Test (1) Test Cases (1) Thread (1) TimSort (1) Top-Down (1) Tournament (1) Tree Rotate (1) Trie vs Hash (1) Triplet (1) Two Stacks (1) Two-End-BFS (1) UyHiP (1) Valid Tree (1) Vector (1) Wiggle Sort (1) Wikipedia (1) ZOJ (1) ZigZag (1) codevs (1) cos126 (1) javabeat (1) jum (1) sqrt(N) (1) 两次dijkstra (1) 九度 (1) 二进制枚举 (1) 夹逼法 (1) 归一化 (1) 折半枚举 (1) 枚举 (1) 状态压缩DP (1) 男人八题 (1) 英雄会 (1) 逆向思维 (1)