Проверка и оптимизация кода - двухстрока общая подстрока
Я решал проблему с двумя строками. Я написал ниже код. Он прошел 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);
}
}
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");
}