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

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

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
}
目录
相关文章
|
2月前
|
程序员 C语言
【C语言】LeetCode(力扣)上经典题目
【C语言】LeetCode(力扣)上经典题目
|
2月前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
90 0
|
2月前
力扣(LeetCode)数据结构练习题(2)
力扣(LeetCode)数据结构练习题(2)
31 0
|
2月前
|
存储
力扣(LeetCode)数据结构练习题
力扣(LeetCode)数据结构练习题
56 0
|
5月前
2670.找出不同元素数目差数组-力扣(LeetCode)
2670.找出不同元素数目差数组-力扣(LeetCode)
36 0
|
3月前
|
Go
Golang语言之管道channel快速入门篇
这篇文章是关于Go语言中管道(channel)的快速入门教程,涵盖了管道的基本使用、有缓冲和无缓冲管道的区别、管道的关闭、遍历、协程和管道的协同工作、单向通道的使用以及select多路复用的详细案例和解释。
136 4
Golang语言之管道channel快速入门篇
|
3月前
|
Go
Golang语言文件操作快速入门篇
这篇文章是关于Go语言文件操作快速入门的教程,涵盖了文件的读取、写入、复制操作以及使用标准库中的ioutil、bufio、os等包进行文件操作的详细案例。
71 4
Golang语言文件操作快速入门篇
|
3月前
|
Go
Golang语言之gRPC程序设计示例
这篇文章是关于Golang语言使用gRPC进行程序设计的详细教程,涵盖了RPC协议的介绍、gRPC环境的搭建、Protocol Buffers的使用、gRPC服务的编写和通信示例。
111 3
Golang语言之gRPC程序设计示例
|
3月前
|
安全 Go
Golang语言goroutine协程并发安全及锁机制
这篇文章是关于Go语言中多协程操作同一数据问题、互斥锁Mutex和读写互斥锁RWMutex的详细介绍及使用案例,涵盖了如何使用这些同步原语来解决并发访问共享资源时的数据安全问题。
100 4
|
3月前
|
Go 调度
Golang语言goroutine协程篇
这篇文章是关于Go语言goroutine协程的详细教程,涵盖了并发编程的常见术语、goroutine的创建和调度、使用sync.WaitGroup控制协程退出以及如何通过GOMAXPROCS设置程序并发时占用的CPU逻辑核心数。
70 4
Golang语言goroutine协程篇