comments	difficulty	edit_url	tags
true	简单	https://github.com/doocs/leetcode/edit/main/solution/3400-3499/3438.Find%20Valid%20Pair%20of%20Adjacent%20Digits%20in%20String/README.md	哈希表 字符串 计数

3438. 找到字符串中合法的相邻数字

English Version

题目描述

给你一个只包含数字的字符串 s 。如果 s 中两个 相邻 的数字满足以下条件，我们称它们是 合法的 ：

• 前面的数字 不等于 第二个数字。
• 两个数字在 s 中出现的次数 恰好 分别等于这个数字本身。

请你从左到右遍历字符串 s ，并返回最先找到的 合法 相邻数字。如果这样的相邻数字不存在，请你返回一个空字符串。

 

示例 1：

输入：s = "2523533"

输出："23"

解释：

数字 '2' 出现 2 次，数字 '3' 出现 3 次。"23" 中每个数字在 s 中出现的次数都恰好分别等于数字本身。所以输出 "23" 。

示例 2：

输入：s = "221"

输出："21"

解释：

数字 '2' 出现 2 次，数字 '1' 出现 1 次。所以输出 "21" 。

示例 3：

输入：s = "22"

输出：""

解释：

没有合法的相邻数字。

 

提示：

• 2 <= s.length <= 100
• s 只包含 '1' 到 '9' 的数字。

解法

方法一：计数

我们可以用一个长度为 $10$ 的数组 $\textit{cnt}$ 记录字符串 $\textit{s}$ 中每个数字出现的次数。

然后我们遍历字符串 $\textit{s}$ 中的相邻数字对，如果这两个数字不相等且满足这两个数字出现的次数分别等于这两个数字本身，我们就找到了一个合法的相邻数字对，返回即可。

遍历结束后，如果没有找到合法的相邻数字对，我们返回一个空字符串。

时间复杂度 $O(n)$，其中 $n$ 为字符串 $\textit{s}$ 的长度。空间复杂度 $O(|\Sigma|)$，其中 $\Sigma$ 为字符串 $\textit{s}$ 中出现的字符集，本题中 $\Sigma = {1, 2, \ldots, 9}$。

Python3

class Solution:
    def findValidPair(self, s: str) -> str:
        cnt = [0] * 10
        for x in map(int, s):
            cnt[x] += 1
        for x, y in pairwise(map(int, s)):
            if x != y and cnt[x] == x and cnt[y] == y:
                return f"{x}{y}"
        return ""

Java

class Solution {
    public String findValidPair(String s) {
        int[] cnt = new int[10];
        for (char c : s.toCharArray()) {
            ++cnt[c - '0'];
        }
        for (int i = 1; i < s.length(); ++i) {
            int x = s.charAt(i - 1) - '0';
            int y = s.charAt(i) - '0';
            if (x != y && cnt[x] == x && cnt[y] == y) {
                return s.substring(i - 1, i + 1);
            }
        }
        return "";
    }
}

C++

class Solution {
public:
    string findValidPair(string s) {
        int cnt[10]{};
        for (char c : s) {
            ++cnt[c - '0'];
        }
        for (int i = 1; i < s.size(); ++i) {
            int x = s[i - 1] - '0';
            int y = s[i] - '0';
            if (x != y && cnt[x] == x && cnt[y] == y) {
                return s.substr(i - 1, 2);
            }
        }
        return "";
    }
};

Go

func findValidPair(s string) string {
	cnt := [10]int{}
	for _, c := range s {
		cnt[c-'0']++
	}
	for i := 1; i < len(s); i++ {
		x, y := int(s[i-1]-'0'), int(s[i]-'0')
		if x != y && cnt[x] == x && cnt[y] == y {
			return s[i-1 : i+1]
		}
	}
	return ""
}

TypeScript

function findValidPair(s: string): string {
    const cnt: number[] = Array(10).fill(0);
    for (const c of s) {
        ++cnt[+c];
    }
    for (let i = 1; i < s.length; ++i) {
        const x = +s[i - 1];
        const y = +s[i];
        if (x !== y && cnt[x] === x && cnt[y] === y) {
            return `${x}${y}`;
        }
    }
    return '';
}