433.最小基因变化
433.最小基因变化
题解
题目:给你一个字符串,和一个合法字符串数组,字符串每次只能变一个字符,并且是"ACGT"其中一个,变之后需要时合法字符串,问能不能变到给定的end字符串
思路:dfs+回溯
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 }