3817. 数字字符串中的好索引 🔒

题目描述

给定一个由数字组成的字符串 s。

如果存在一个子串，它以索引 i 结尾并且等于 i 的十进制表示，则称索引 i 为好索引。

返回一个包含所有好索引的整数数组，并按 升序排列。

示例 1：

输入：s = "0234567890112"

输出：[0,11,12]

解释：

在索引 0 处，索引的十进制表示为 "0"。子串 s[0] 是 "0"，匹配成功，所以索引 0 是好的。
在索引 11 处，索引的十进制表示是 "11"。子串 s[10..11] 是 "11"，匹配成功，所以索引 11 是好的。
在索引 12 处，索引的十进制表示是 "12"。子串 s[11..12] 是 "12"，匹配成功，所以索引 12 是好的。

没有其他索引在其结束处有一个子串等于其十进制表示。因此，答案是 [0, 11, 12]。

示例 2：

输入：s = "01234"

输出：[0,1,2,3,4]

解释：

对于 0 到 4 的每个索引 i，i 的十进制表示都是单个数字，并且子串 s[i] 匹配这个数字。

因此，每个索引都存在一个有效的子字符串，使得所有索引都是好的。

示例 3：

输入：s = "12345"

输出：[]

解释：

没有索引的子字符串以它结尾并与它的十进制表示匹配。

因此，没有好索引，结果是一个空数组。

提示：

1 <= s.length <= 10⁵
s 只包含 '0' 到 '9' 的数字。

解法

方法一：模拟

我们注意到，字符串 \(s\) 的长度最大为 \(10^5\)，而索引 \(i\) 的十进制表示的长度最多为 \(6\)（因为 \(10^5\) 的十进制表示为 \(100000\)，长度为 \(6\)）。因此，我们只需要检查每个索引 \(i\) 的十进制表示对应的子串是否与之相等。

时间复杂度 \(O(n)\)，其中 \(n\) 是字符串 \(s\) 的长度。忽略答案的空间消耗，空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScript

class Solution:
    def goodIndices(self, s: str) -> List[int]:
        ans = []
        for i in range(len(s)):
            t = str(i)
            k = len(t)
            if s[i + 1 - k : i + 1] == t:
                ans.append(i)
        return ans

class Solution {
    public List<Integer> goodIndices(String s) {
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            String t = String.valueOf(i);
            int k = t.length();
            if (s.substring(i + 1 - k, i + 1).equals(t)) {
                ans.add(i);
            }
        }
        return ans;
    }
}

class Solution {
public:
    vector<int> goodIndices(string s) {
        vector<int> ans;
        for (int i = 0; i < s.size(); i++) {
            string t = to_string(i);
            int k = t.size();
            if (s.substr(i + 1 - k, k) == t) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};

func goodIndices(s string) (ans []int) {
    for i := range s {
        t := strconv.Itoa(i)
        k := len(t)
        if s[i+1-k:i+1] == t {
            ans = append(ans, i)
        }
    }
    return
}

function goodIndices(s: string): number[] {
    const ans: number[] = [];
    for (let i = 0; i < s.length; i++) {
        const t = String(i);
        const k = t.length;
        if (s.slice(i + 1 - k, i + 1) === t) {
            ans.push(i);
        }
    }
    return ans;
}

3817. 数字字符串中的好索引 🔒

题目描述

解法

方法一：模拟

评论