Манипулирование строковыми данными с помощью карт для очень большого ввода данных

Question

Я решил Две строки проблема в HackerRank

Вот проблема.

Учитывая две строки, определите, имеют ли они общую подстроку. Подстрока может быть всего одним символом.

Например, слова "a", "и", "art" имеют общую подстроку. Слова «be» и «cat» не разделяют подстроку.

Описание функции

Завершите функцию twoStrings в редакторе ниже. Он должен возвращать строку, YES или NO, в зависимости от того, разделяют ли строки общую подстроку.

twoStrings имеет следующие параметры:

s1, s2: две строки для анализа.

Выходной формат

Для каждой пары строк верните YES или NO.

Однако, когда подвергаются слишком длинные строки, мой код не выполняется в течение срока. Есть предложения по повышению эффективности? Я думаю, что могу улучшить поиск подстрок с помощью Stream API. Но я не уверен, как использовать это в этом контексте. Может ли кто-нибудь помочь мне лучше понять это?

public static void main(String[] args) {
    String s1 = "hi";
    String s2 = "world";
    checkSubStrings(s1, s2);
}

static void checkSubStrings(String s1, String s2) {
    Map<String, Long> s1Map = new HashMap<>();
    Map<String, Long> s2Map = new HashMap<>();
    findAllSubStrings(s1, s1Map);
    findAllSubStrings(s2, s2Map);
    boolean isContain = s2Map.entrySet().stream().anyMatch(i -> s1Map.containsKey(i.getKey()) );
    if (isContain) {
        System.out.println("YES");
    } else {
        System.out.println("NO");
    }
}

static void findAllSubStrings(String s, Map<String, Long> map) {
    for (int i = 0; i < s.length(); i++) {
        String subString = s.substring(i);
        for (int j = subString.length(); j > 0; j--) {
            String subSubString = subString.substring(0, j);
            if (map.containsKey(subSubString)) {
                map.put(subSubString, map.get(subSubString) + 1);
            } else {
                if (!subSubString.equals(""))
                    map.put(subSubString, 1L);
            }
        }
    }
}

Обновление

Я только что решил вопрос с помощью HashSets.

Я оптимизировал код используя Set. Теперь он работает с очень большими строками.

static String twoStrings(String s1, String s2) {
    String result = null;
    Set<Character> s1Set = new HashSet<>();
    Set<Character> s2Set = new HashSet<>();
    for(char a : s1.toCharArray()){
        s1Set.add(a);
    }
    for(char a : s2.toCharArray()){
        s2Set.add(a);
    }
    boolean isContain = s2Set.stream().anyMatch(s1Set::contains);

    if(isContain){
        result = "YES";
    } else {
        result = "NO";
    }
    return result;
}

Answer 1

Если 2 строки имеют общую символьную подстроку N (> = 2), они также совместно используют N-1 символьную подстроку (потому что вы можете вырезать символ из конца общей подстроки, и это все равно будет найдено в обеих строках ). Расширяя этот аргумент, они также разделяют 1-символьную подстроку.

Таким образом, все, что вам нужно проверить, это односимвольные подстроки.

Вместо этого заполните свои карты односимвольными подстроками, и Вы избежите создания (и проверки) ненужных подстрок. (И просто используйте набор вместо карты, вы никогда не используете счет).

// Yields a `Set<Integer>`, which can be used directly to check.
return s.codePoints().boxed().collect(Collectors.toSet());