字符串及其反转中是否存在同一字符串

字符串及其反转中是否存在同一字符串(easy)

做题过程

用哈希表，和两数之和一个思路。

算法概述

本题要求为如题所示。

时间复杂度为O(n)
空间复杂度为O(n)

JAVA

class Solution {
    public boolean isSubstringPresent(String s) {
        if (s.length() < 2) {
            return false; // 无法提取两个字符的子字符串
        }

        // 哈希集合存储见过的字符串
        Set<String> seen = new HashSet<>();

        for (int i = 0; i < s.length() - 1; i++) { 
            String temp = s.substring(i, i + 2);
            String reversed = new StringBuilder(temp).reverse().toString();

            // 检查反转
            if (seen.contains(reversed)||temp.equals(reversed)) { 
                return true;
            }

            // 添加当前子字符串
            seen.add(temp); 
        }

        return false;
    }
}

总结

除了这么做还可以不用额外的空间，直接对原字符串反转然后判断反转后的字符串是否存在当前遍历到的子字符串，但这样的问题是时间复杂度是平方，虽然在小规模数据上哈希集合由于查询操作也会消耗常数时间，没这个快，但是大规模哈希集合的表现就会更好。