0

我正在解决两个字符串问题。我写了下面的代码。它通过了 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);
}
}
4

1 回答 1

0

您当前正在做的是 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");
}
于 2015-06-30T17:24:58.653 回答