3884. 双端字符匹配

题目描述

给你一个长度为 n 的字符串 s，其中只包含小写英文字母。

返回最小的下标 i，使得 s[i] == s[n - i - 1]。

如果不存在这样的下标，返回 -1。

示例 1：

输入： s = "abcacbd"

输出： 1

解释：

在下标 i = 1 处，s[1] 和 s[5] 的值均为 'b'。

没有更小的下标满足条件，因此答案是 1。

示例 2：

输入： s = "abc"

输出： 1

解释：

在下标 i = 1 处，左右对应位置重合，因此字符均为 'b'。

没有更小的下标满足条件，因此答案是 1。

示例 3：

输入： s = "abcdab"

输出： -1

解释：

对于每个下标 i，位置 i 和 n - i - 1 的字符均不相同。

因此，不存在有效下标，答案是 -1。

提示：

1 <= n == s.length <= 100
s 仅包含小写英文字母。

解法

方法一：模拟

我们遍历字符串 \(s\) 的前半部分，对于每个下标 \(i\)，我们比较位置 \(i\) 和位置 \(n - i - 1\) 的字符是否相同。如果相同，我们返回下标 \(i\)。如果遍历结束后没有找到满足条件的下标，我们返回 -1。

时间复杂度 \(O(n)\)，其中 \(n\) 是字符串 \(s\) 的长度。空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScript

class Solution:
    def firstMatchingIndex(self, s: str) -> int:
        for i in range(len(s) // 2 + 1):
            if s[i] == s[-i - 1]:
                return i
        return -1

class Solution {
    public int firstMatchingIndex(String s) {
        int n = s.length();
        for (int i = 0; i < n / 2 + 1; ++i) {
            if (s.charAt(i) == s.charAt(n - i - 1)) {
                return i;
            }
        }
        return -1;
    }
}

class Solution {
public:
    int firstMatchingIndex(string s) {
        int n = s.size();
        for (int i = 0; i < n / 2 + 1; ++i) {
            if (s[i] == s[n - i - 1]) {
                return i;
            }
        }
        return -1;
    }
};

func firstMatchingIndex(s string) int {
    n := len(s)
    for i := 0; i < n/2+1; i++ {
        if s[i] == s[n-i-1] {
            return i
        }
    }
    return -1
}

function firstMatchingIndex(s: string): number {
    const n = s.length;
    for (let i = 0; i < Math.floor(n / 2) + 1; i++) {
        if (s[i] === s[n - i - 1]) {
            return i;
        }
    }
    return -1;
}

3884. 双端字符匹配

题目描述

解法

方法一：模拟

评论