mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-04 16:12:47 +08:00
28 lines
656 B
Go
28 lines
656 B
Go
package leetcode
|
|
|
|
func pyramidTransition(bottom string, allowed []string) bool {
|
|
pyramid := make(map[string][]string)
|
|
for _, v := range allowed {
|
|
pyramid[v[:len(v)-1]] = append(pyramid[v[:len(v)-1]], string(v[len(v)-1]))
|
|
}
|
|
return dfsT(bottom, "", pyramid)
|
|
}
|
|
|
|
func dfsT(bottom, above string, pyramid map[string][]string) bool {
|
|
if len(bottom) == 2 && len(above) == 1 {
|
|
return true
|
|
}
|
|
if len(bottom) == len(above)+1 {
|
|
return dfsT(above, "", pyramid)
|
|
}
|
|
base := bottom[len(above) : len(above)+2]
|
|
if data, ok := pyramid[base]; ok {
|
|
for _, key := range data {
|
|
if dfsT(bottom, above+key, pyramid) {
|
|
return true
|
|
}
|
|
}
|
|
}
|
|
return false
|
|
}
|