golang力扣leetcode 433. 最小基因变化

1.这里每次只能变一次，很容易想到dfs+mp判断是否合法
2.但是存在A->B->A的情况,需要把之前的字符串设为vis=true，之后再回溯掉
3.并且可能有多种路径变化，只需记录第一次的最短路径即可

func minMutation(start, end string, bank []string) int {
  mp := make(map[string]bool)
  vis := make(map[string]bool)
  for _, v := range bank {
    mp[v] = true
  }
  ans := math.MaxInt32
  dirs := []byte("ACGT")
  var dfs func(cur string, step int)
  dfs = func(cur string, step int) {
    if cur == end {
      ans = step
      return
    }
    vis[cur] = true
    for i := 0; i < 8; i++ {
      for _, v := range dirs {
        temp := []byte(cur)
        if v != temp[i] {
          temp[i] = v
          cnt := string(temp)
          if ans != math.MaxInt32 || !mp[cnt] || vis[cnt] {
            continue
          }
          dfs(string(temp), step+1)
        }
      }
    }
    vis[cur] = false
  }
  dfs(start, 0)
  if ans == math.MaxInt32 {
    return -1
  }
  return ans
}