跳转至

3817. Good Indices in a Digit String 🔒

题目描述

You are given a string s consisting of digits.

An index i is called good if there exists a substring of s that ends at index i and is equal to the decimal representation of i.

Return an integer array of all good indices in increasing order.

 

Example 1:

Input: s = "0234567890112"

Output: [0,11,12]

Explanation:​​​​​​​

  • At index 0, the decimal representation of the index is "0". The substring s[0] is "0", which matches, so index 0 is good.

  • At index 11, the decimal representation is "11". The substring s[10..11] is "11", which matches, so index 11 is good.

  • At index 12, the decimal representation is "12". The substring s[11..12] is "12", which matches, so index 12 is good.

No other index has a substring ending at it that equals its decimal representation. Therefore, the answer is [0, 11, 12].

Example 2:

Input: s = "01234"

Output: [0,1,2,3,4]

Explanation:

For every index i from 0 to 4, the decimal representation of i is a single digit, and the substring s[i] matches that digit.

Therefore, a valid substring ending at each index exists, making all indices good.

Example 3:

Input: s = "12345"

Output: []

Explanation:

No index has a substring ending at it that matches its decimal representation.

Therefore, there are no good indices and the result is an empty array.

 

Constraints:

  • 1 <= s.length <= 105
  • s only consists of digits from '0' to '9'.

解法

方法一：模拟

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

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

1
2
3
4
5
6
7
8
9
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
}

评论