活字印刷 回溯剪枝
0 / 0 / 创建于 4年前 /
pardon110 的个人博客
活字印刷
你有一套活字字模 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 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号