leetcode 756. 金字塔转换矩阵

题解

递归,通过bottom找出下一层字符串next,判断是否可以最终找到长度为1的的顶层字符串

示例代码(go)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func pyramidTransition(bottom string, allowed []string) bool {
return canTrans(bottom, "", allowed)
}

func canTrans(bottom, next string, allowed []string) bool {
if len(bottom) == 1 {
return true
}
if len(bottom) - len(next) > 1 {
can := false
for _, str := range allowed {
if bottom[len(next)] == str[0] && bottom[len(next)+1] == str[1] {
can = can || canTrans(bottom, next+string(str[2]), allowed)
}
}
return can
} else {
return canTrans(next, "", allowed)
}
}