- Minimum Genetic Mutation problem link: https://leetcode.com/problems/minimum-genetic-mutation/
I used BFS to solve this problem in C#, having no idea how does the following C# code got runtime error on LeetCode. (I have checked that this code works in C/C++) The problem seems to have something wrong inside BFS. I have tried another way to code in C# and it got accepted, but in my thought these two code are in the same logic, how does the first code lead to runtime error?
Runtime Error Message: Unhandled exception. System.NullReferenceException: Object reference not set to an instance of an object.
At Solution.MinMutation(String start, String end, String[] bank)
At __Driver__.Main(String[] args)
Last executed input: "AACCGGTT"
"AACCGGTA"
["AACCGGTA"]
RE Code
public class Solution {
public int MinMutation(string start, string end, string[] bank) {
Queue<int> q = new Queue<int>();
int eid = -1;
int[] dis = new int[bank.Length];
for(int i = 0; i < bank.Length; i ++) {
if(end == bank[i]) eid = i;
dis[i] = -1;
}
if(eid == -1) return -1;
q.Enqueue(-1);
while(q.Count > 0) {
int tp = q.Dequeue();
for(int i = 0; i < bank.Length; i ++) {
if(dis[i] != -1) continue;
int cnt = 0;
for(int j = 0; j < 8; j ++) {
if(tp == -1) {
if(bank[i][j] != start[j]) cnt ++;
}
else {
if(tp >= 0 && tp < bank.Length) {
if(bank[i][j] != bank[tp][j]) cnt ++;
}
}
}
if(cnt == 1) {
dis[i] = (tp == -1? 0 : dis[tp]) + 1;
q.Enqueue(i);
}
}
}
return dis[eid];
}
}
AC Code (BFS Part)
while(q.Count > 0) {
int tp = q.Dequeue();
for(int i = 0; i < bank.Length; i ++) {
if(dis[i] != -1) continue;
int cnt = 0;
if(tp == -1) {
for(int j = 0; j < 8; j ++) {
if(bank[i][j] != start[j]) cnt ++;
}
}
else {
for(int j = 0; j < 8; j ++) {
if(tp >= 0 && tp < bank.Length) {
if(bank[i][j] != bank[tp][j]) cnt ++;
}
}
}
if(cnt == 1) {
dis[i] = (tp == -1? 0 : dis[tp]) + 1;
q.Enqueue(i);
}
}
}