【Lintcode】1630. Interesting String

题目地址：

https://www.lintcode.com/problem/interesting-string/description

给定一个字符串$s$，只含数字和小写字母。问$s$是否可以拆成若干子串，使得每个子串都是$n+a$的形式，其中$n$是一个数字（可以不是一位数），$a$是长度为$n$的字符串。如果可以，则返回”yes“，否则返回”no“。

思路是DFS。枚举$n$的长度，然后看一下后面截取出长度为$n$的子串之后的一位是否是数字，如果是，则进行下一层DFS继续枚举，如果能一路枚举到$s$末尾，则说明可以，返回”yes“。为了加速，可以用一个数组$m$，其中$m[i]$代表$s[i:]$是否可以拆分成满足条件的形式。这样一旦发现$m[i]$是false，则可以直接返回false不用重复枚举。代码如下：

import java.util.Arrays;public class Solution {
    /*** @param s: the string s* @return: check if the string is interesting*/public String check(String s) {
    // Write your code hereboolean[] memo = new boolean[s.length()];Arrays.fill(memo, true);return dfs(0, s, memo) ? "yes" : "no";}private boolean dfs(int pos, String s, boolean[] memo) {
    // 恰好枚举到s末尾，返回trueif (pos == s.length()) {
    return true;}// 字符数不够，返回falseif (pos > s.length()) {
    return false;}// 不是数字，返回falseif (!Character.isDigit(s.charAt(pos))) {
    return false;}// 之前记忆的时候是false，返回falseif (!memo[pos]) {
    return false;}// 枚举n为s[i : pos]for (int i = pos; i < s.length(); i++) {
    if (Character.isDigit(s.charAt(i))) {
    int len = Integer.parseInt(s.substring(pos, i + 1)), next = i + len + 1;if (dfs(next, s, memo)) {
    return true;}} else {
    // 遇到第一个不是数字的字符了，直接退出循环break;}}// 返回前做记忆memo[pos] = false;return false;}
}

时间复杂度是指数级，空间$O(l_s)$。