活字印刷 回溯剪枝

活字印刷

你有一套活字字模 tiles,其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。

输入:"AAB"
输出:8
解释:可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"

分析

  • 排序去重
  • 全排列计数
  • 回溯剪枝

上码

func numTilePossibilities(tiles string) int {

    var cnt int
    var backtrace func([]byte, []bool)

    N := len(tiles)         // 计算字节数 
    by := []byte(tiles)     // 排序方便去重
    sort.Slice(by,func(i,j int)bool{
        return by[i] < by[j]
    })

    // 全排列
    backtrace = func(path []byte, vis []bool){
        if len(path) == N {
            return 
        }
        for i:=0;i < N;i++{
            if vis[i] || i > 0 && by[i]==by[i-1] && !vis[i-1] {
                continue
            }
            cnt++  // 此处计数,则包含子集全排列数
            vis[i] = true
            backtrace(append(path, by[i]),vis)
            vis[i] = false
        }
    }
    backtrace([]byte{},make([]bool, N))

    return cnt
}

性能

提交时间 提交结果 运行时间 内存消耗 语言
几秒前 通过 0 ms 1.9 MB Go
本作品采用《CC 协议》,转载必须注明作者和本文链接
pardon110
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
开发者 @ 社科大
文章
125
粉丝
16
喜欢
92
收藏
46
排名:99
访问:4.7 万
私信
所有博文