HackerRank Two Strings题Java代码未通过测试用例2问题求解

核心错误原因 #

你写的代码存在两个致命逻辑错误，导致无法通过测试用例：

• 子串判断逻辑错误：题目要求的公共子串最小长度为1即可，只要两个字符串存在任意一个公共字符就返回YES。你当前代码判断的是「短字符串从索引i到末尾的完整后缀」是否存在于长字符串中，而非判断是否有任意公共子串。比如测试用例里的audvark和apple有公共字符a，但你的代码判断的是audvark、udvark、dvark等完整后缀是否存在于apple里，自然无法匹配成功。
• 结果被后续遍历覆盖：哪怕某次遍历找到了匹配的子串，后续遍历如果遇到不匹配的情况，answer会被重新赋值为NO，最终返回的是最后一次遍历的结果，而非只要找到一次就返回YES。

修复方案 #

优化版实现（时间复杂度O(n+m)，效率更高） #

import java.util.HashSet;
import java.util.Set;

public static String twoStrings(String s1, String s2) {
    // 选择较短的字符串存字符集合，降低空间消耗
    String shortStr = s1.length() <= s2.length() ? s1 : s2;
    String longStr = s1.length() > s2.length() ? s1 : s2;

    Set<Character> charSet = new HashSet<>();
    for (char c : shortStr.toCharArray()) {
        charSet.add(c);
    }

    // 遍历长字符串，只要有一个字符在集合中就直接返回YES
    for (char c : longStr.toCharArray()) {
        if (charSet.contains(c)) {
            return "YES";
        }
    }
    return "NO";
}

基于原逻辑的最小修改版 #

如果你要保留原代码的遍历逻辑，只需要修改子串截取逻辑，同时匹配成功后提前终止循环即可：

public static String twoStrings(String s1, String s2) {
    String answer = "NO"; 
    String stringToIterate = "";
    String theOtherString = "";

    if (s1.length() > s2.length()) {
        stringToIterate = s2;
        theOtherString  = s1;
    } else {
        stringToIterate = s1;
        theOtherString = s2;
    }

    for (int i= 0; i < stringToIterate.length();i++) {
        // 只截取单个字符作为子串判断
        String subS = stringToIterate.substring(i, i+1);
        if (theOtherString.contains(subS)) {
            answer = "YES";
            // 匹配成功直接终止循环，避免结果被覆盖
            break;
        }
    }
    return answer;
}

内容的提问来源于stack exchange，提问作者Vanessa