[LeetCode] 每日一题 3083. 字符串及其反转中是否存在同一子字符串

题目链接

题目描述

给你一个字符串 s ，请你判断字符串 s 是否存在一个长度为 2 的子字符串，在其反转后的字符串中也出现。

如果存在这样的子字符串，返回 true；如果不存在，返回 false 。

示例输入

示例 1

输入：s = "leetcode"

输出：true

解释：子字符串 "ee" 的长度为 2，它也出现在 reverse(s) == "edocteel" 中。

示例 2

输入：s = "abcba"

输出：true

解释：所有长度为 2 的子字符串 "ab"、"bc"、"cb"、"ba" 也都出现在 reverse(s) == "abcba" 中。

示例 3

输入：s = "abcd"

输出：false

解释：字符串 s 中不存在满足「在其反转后的字符串中也出现」且长度为 2 的子字符串。

提示

• 1 <= s.length <= 100

• 字符串 s 仅由小写英文字母组成

题解

解题思路

1. 记录子字符串关系
   我们使用一个二维布尔数组 group 来模拟哈希表记录长度为 2 的子字符串是否存在。group[i][j] 表示字符 i + 'a' 和 j + 'a' 组成的子字符串是否在字符串中出现过

2. 遍历字符串

   • 遍历字符串的每一对相邻字符，提取出长度为 2 的子字符串

   • 记录当前子字符串在 group 中的存在性

   • 同时检查该子字符串的反转形式是否已存在。若已存在，直接返回 true

3. 返回结果

   • 如果遍历完成未发现反转的子字符串，则返回 false

代码实现

class Solution {
    public boolean isSubstringPresent(String s) {
        // 创建一个 26*26 的布尔数组，记录子字符串存在性
        boolean[][] group = new boolean[26][26];
        
        // 遍历字符串中的所有相邻字符对
        for (int i = 1; i < s.length(); i++) {
            // 获取当前子字符串的两个字符的索引
            int first = s.charAt(i - 1) - 'a';
            int second = s.charAt(i) - 'a';
            
            // 标记当前子字符串存在
            group[first][second] = true;
            
            // 检查反转的子字符串是否已存在
            if (group[second][first]) {
                return true;
            }
        }
        
        // 未找到符合条件的子字符串，返回 false
        return false;
    }
}

复杂度分析

1. 时间复杂度

   • 遍历字符串：耗时 O(n)，其中 n 是字符串的长度

   • 查找和更新二维布尔数组的元素：每次操作耗时 O(1)

   • 总体时间复杂度为 O(n)

2. 空间复杂度

   • 使用了一个 26×26 的布尔数组，空间复杂度为 O(1)，因为它的大小与输入字符串无关

总结

该解法利用二维数组记录子字符串存在性，避免了暴力搜索的高时间复杂度，效率较高，适用于字符串长度较大的情况
优点：

• 时间复杂度低，运行效率高

• 代码简洁，易于理解

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。