Easy

题目描述

给你一个只包含数字的字符串 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’

提示：

  • 使用哈希表统计每个数字的频率

解题思路

这道题需要我们找到满足两个条件的相邻数字对：

  1. 两个数字不相等
  2. 每个数字的出现次数等于其数值

解题思路：

首先统计字符串中每个数字的出现频率。然后从左到右遍历字符串，检查每对相邻的数字是否满足条件。

具体步骤：

  1. 使用哈希表记录每个数字在字符串中的出现次数
  2. 遍历字符串，对于每个位置 i（i < n-1），检查 s[i] 和 s[i+1]：
    • 如果两个数字不相等
    • 且 s[i] 的出现次数等于其数值
    • 且 s[i+1] 的出现次数等于其数值
    • 则返回这个数字对
  3. 如果遍历结束都没找到有效对，返回空字符串

这个解法的时间复杂度是 O(n)，空间复杂度是 O(1)（因为数字只有1-9，哈希表大小固定）。

代码实现

class Solution {
public:
    string findValidPair(string s) {
        unordered_map<char, int> count;
        for (char c : s) {
            count[c]++;
        }
        
        for (int i = 0; i < s.length() - 1; i++) {
            char first = s[i];
            char second = s[i + 1];
            
            if (first != second && 
                count[first] == (first - '0') && 
                count[second] == (second - '0')) {
                return string(1, first) + string(1, second);
            }
        }
        
        return "";
    }
};

class Solution:
    def findValidPair(self, s: str) -> str:
        count = {}
        for c in s:
            count[c] = count.get(c, 0) + 1
        
        for i in range(len(s) - 1):
            first = s[i]
            second = s[i + 1]
            
            if (first != second and 
                count.get(first, 0) == int(first) and 
                count.get(second, 0) == int(second)):
                return first + second
        
        return ""

public class Solution {
    public string FindValidPair(string s) {
        Dictionary<char, int> count = new Dictionary<char, int>();
        foreach (char c in s) {
            if (count.ContainsKey(c)) {
                count[c]++;
            } else {
                count[c] = 1;
            }
        }
        
        for (int i = 0; i < s.Length - 1; i++) {
            char first = s[i];
            char second = s[i + 1];
            
            if (first != second && 
                count.GetValueOrDefault(first, 0) == (first - '0') && 
                count.GetValueOrDefault(second, 0) == (second - '0')) {
                return first.ToString() + second.ToString();
            }
        }
        
        return "";
    }
}

var findValidPair = function(s) {
    const count = {};
    for (let char of s) {
        count[char] = (count[char] || 0) + 1;
    }
    
    for (let i = 0; i < s.length - 1; i++) {
        const first = s[i];
        const second = s[i + 1];
        
        if (first !== second && 
            count[first] === parseInt(first) && 
            count[second] === parseInt(second)) {
            return first + second;
        }
    }
    
    return "";
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n)
空间复杂度O(1)

说明：

  • 时间复杂度：需要遍历字符串两次，一次统计频率，一次查找有效对，总体为 O(n)
  • 空间复杂度：哈希表最多存储 9 个不同的数字，空间使用量为常数级别，所以是 O(1)

相关题目