Description

There is now a string s consisting of only numbers and lowercase letters.

If the string s is interesting, then s must be split into several substrings, each substring satisfies the beginning of the number, and the number represents the number of characters after it. For example, s = “4g12y6hunter”, we can divide it into “4g12y” and “6hunter”, so the string is interesting.

If s is an interesting string, output “yes”, otherwise output “no”

Example:

s = "124gray6hunter",return "yes"

we can divide it into "12", "4gray", "6hunter".

s = "31ba2a" ,return "no"

判断字符串s是否“有趣”。

有趣:字符串可以被分成多组,每组前面的数字等于剩余字符的长度。

Solution

本题主要在于需要识别连续数字,比如11需要理解为十一

使用BFS实现:识别数字,跳过对应长度的字符后,将下一个检查点加入队列。

BFS
  • golang
  • cpp
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
func check(s string) string {
    sLength := len(s)

    if sLength <= 0 {
        return "no"
    }

    queue := []int{0}

    var idx, n, num, nextIdx int
    for len(queue) > 0 {
        // pop front
        idx = queue[0]
        queue = queue[1:]

        n = 0
        for idx < sLength {
            num = int(s[idx] - byte('0'))
            if num < 0 || num > 9 {
                break
            }
            n = n*10 + num

            // 从当前位置向后跳过 n 个字符
            // 并且检查下一个字符是否为数字或者恰好结束
            nextIdx = idx + n + 1

            if nextIdx > sLength {
                break
            } else if nextIdx == sLength {
                // 当前位置恰好结束
                return "yes"
            } else if nextIdx != idx {
                // push back
                queue = append(queue, nextIdx)
            }
            idx++
        }
    }

    return "no"
}