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
<span class="k">if</span> <span class="nx">sLength</span> <span class="o">&lt;=</span> <span class="mi">0</span> <span class="p">{</span>
    <span class="k">return</span> <span class="s">&#34;no&#34;</span>
<span class="p">}</span>

<span class="nx">queue</span> <span class="o">:=</span> <span class="p">[</span><span class="p">]</span><span class="kt">int</span><span class="p">{</span><span class="mi">0</span><span class="p">}</span>

<span class="kd">var</span> <span class="nx">idx</span><span class="p">,</span> <span class="nx">n</span><span class="p">,</span> <span class="nx">num</span><span class="p">,</span> <span class="nx">nextIdx</span> <span class="kt">int</span>
<span class="k">for</span> <span class="nb">len</span><span class="p">(</span><span class="nx">queue</span><span class="p">)</span> <span class="p">&gt;</span> <span class="mi">0</span> <span class="p">{</span>
    <span class="c1">// pop front

idx = queue[0] queue = queue[1:]

    <span class="nx">n</span> <span class="p">=</span> <span class="mi">0</span>
    <span class="k">for</span> <span class="nx">idx</span> <span class="p">&lt;</span> <span class="nx">sLength</span> <span class="p">{</span>
        <span class="nx">num</span> <span class="p">=</span> <span class="nb">int</span><span class="p">(</span><span class="nx">s</span><span class="p">[</span><span class="nx">idx</span><span class="p">]</span> <span class="o">-</span> <span class="nb">byte</span><span class="p">(</span><span class="sc">&#39;0&#39;</span><span class="p">)</span><span class="p">)</span>
        <span class="k">if</span> <span class="nx">num</span> <span class="p">&lt;</span> <span class="mi">0</span> <span class="o">||</span> <span class="nx">num</span> <span class="p">&gt;</span> <span class="mi">9</span> <span class="p">{</span>
            <span class="k">break</span>
        <span class="p">}</span>
        <span class="nx">n</span> <span class="p">=</span> <span class="nx">n</span><span class="o">*</span><span class="mi">10</span> <span class="o">+</span> <span class="nx">num</span>

        <span class="c1">// 从当前位置向后跳过 n 个字符

// 并且检查下一个字符是否为数字或者恰好结束 nextIdx = idx + n + 1

        <span class="k">if</span> <span class="nx">nextIdx</span> <span class="p">&gt;</span> <span class="nx">sLength</span> <span class="p">{</span>
            <span class="k">break</span>
        <span class="p">}</span> <span class="k">else</span> <span class="k">if</span> <span class="nx">nextIdx</span> <span class="o">==</span> <span class="nx">sLength</span> <span class="p">{</span>
            <span class="c1">// 当前位置恰好结束

return "yes" } else if nextIdx != idx { // push back queue = append(queue, nextIdx) } idx++ } }

<span class="k">return</span> <span class="s">&#34;no&#34;</span>

}