LintCode 1630. Interesting String

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

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"

}

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";
}

};