代码校验与优化——两个String的公共子串

Question

我正在解决 Two String 问题。我写了下面的代码。它通过了 4 个测试用例，但有两个测试用例显示超时。请告诉我如何优化它以避免超时？也欢迎任何解释和显示此类优化示例的链接。

  public class TwoStrings
{
     private static final String YES = "YES";
private static final String NO  = "NO";

public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int testCases = Integer.parseInt(in.nextLine());
String input1[] = new String[testCases];
String input2[] = new String[testCases];

for (int i = 0; i < testCases; i++)
{
    input1[i] = in.nextLine();
    input2[i] = in.nextLine();
}
in.close();

for (int i = 0; i < testCases; i++)
{
    displayResult(input1[i], input2[i]);
}
}

private static void displayResult(String string1, String string2)
{
// choosing smaller String for iterating through it.
String smallerString = string1.length() <= string2.length() ? string1
    : string2;
String biggerString = string1 == smallerString ? string2 : string1;

boolean constains = false;

// Concept - Even if single letter is common, substring exists.
// So checking just one string.
for (int i = 0; i < smallerString.length(); i++)
{
    if (biggerString.contains(String.valueOf(smallerString.charAt(i))))
    {
    constains = true;
    break;
    }
}

if (constains)
    System.out.println(YES);
else
    System.out.println(NO);
}
}

Answer 1

你目前正在做的是 O(n^2) 因为你遍历了小字符串并且在较长的字符串中搜索该字符是线性搜索因为它没有排序（所有字母按字母顺序排列） .

下面是一个 O(n) 的解决方案。这个概念是有一个大小为 26 的布尔数组（每个字母一个），如果字母在小字符串（实际上可以是小字符串或长字符串，无关紧要）中，则使索引为真。从小字符串创建数组是 O(n)，检查长字符串中的字母是 O(n)，总计 O(n + n)，减少到 O(n).

private static void displayResult(String string1, String string2)
{
    boolean[] contains = new boolean[26];
    boolean noSubstring = true;

    // populate the contains array
    for (char c : string1.toCharArray())
    {
        int value = (int)c - (int)'a';    // make the char 0-25
        contains[value] = true;
    }

    for (char c : string2.toCharArray())
    {
        int value = (int)c - (int)'a';    // make the char 0-25

        if (contains[value])
        {
            noSubstring = false;
            break;
        }
    }

    if (noSubstring)   System.out.println("NO");
    else               System.out.println("YES");
}

代码校验与优化——两个String的公共子串

Code verifcation and optimization - Two String common substring

java

string

subsequence