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"
1
| we can divide it into "12", "4gray", "6hunter".
|
s = "31ba2a" ,return "no"
判断字符串s是否“有趣”。
有趣：字符串可以被分成多组，每组前面的数字等于剩余字符的长度。
Solution
本题主要在于需要识别连续数字，比如11需要理解为十一。
使用BFS实现：识别数字，跳过对应长度的字符后，将下一个检查点加入队列。
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
| <!-- tab golang -->
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"
}
<!-- endtab -->
<!-- tab cpp -->
class Solution {
public:
/**
* @param s: the string s
* @return: check if the string is interesting
*/
string check(string &s) {
// Write your code here
int sLength = s.length();
if (sLength == 0) {
return "no";
}
queue<int> q;
q.push(0);
int idx, n, num, nextIdx;
while (q.size() > 0) {
// pop front
int idx = q.front();
q.pop();
n = 0;
for (; idx < sLength; idx++) {
num = s[idx] - (int)'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
q.push(nextIdx);
}
}
}
return "no";
}
};
<!-- endtab -->
|