Finding words in long string within edit distance ignoring whitespace

Question

I am looking for a algorithm to efficiently search for words within given edit distance in a query string while ignoring whitespace.

For e.g. If words on which I need to build an index are:

OHIO, WELL

and query String:

HELLO HI THERE H E L L O WORLD WE LC OME

For edit distance 1, I need output:

HELL, O HI T, H E L L, WE LC

For ignoring whitespace part, perhaps we can remove all spaces, but I can't find any algorithm that search text fuzzily in a string without spaces.

I have done lot of research without any success. Please let me know if the question is unclear or need more information.

Answer 1

public static void main(String[] args) {
    System.out.println(getMatches(List.of("OHIO", "WELL"), "HELLO HI THERE H E L L O WORLD WE LC OME", 1));
}

private static List<String> getMatches(List<String> words, String query, int editDistance) {
    return words.stream()
            .flatMap(w -> getMatches(w, query, editDistance).stream().map(String::trim))
            .distinct()
            .collect(Collectors.toList());
}

private static List<String> getMatches(String word, String query, int editDistance) {
    List<String> matches = new ArrayList<>();
    for (int i = 0; i < query.length(); i++) {
        StringBuilder candidate = new StringBuilder();
        StringBuilder candidateWithoutSpaces = new StringBuilder();
        populateCandidates(word, query, i, candidate, candidateWithoutSpaces);
        if (isMatch(candidateWithoutSpaces, word, editDistance)) matches.add(candidate.toString());
    }
    return matches;
}

private static boolean isMatch(StringBuilder candidateWithoutSpaces, String word, int editDistance) {
    if (candidateWithoutSpaces.length() != word.length()) return false;
    for (int i = 0; i < candidateWithoutSpaces.length(); i++) {
        if (candidateWithoutSpaces.charAt(i) != word.charAt(i) && --editDistance < 0) return false;
    }
    return true;
}

private static void populateCandidates(String word, String query, int i, StringBuilder candidate, StringBuilder candidateWithoutSpaces) {
    int j = 0;
    while (candidateWithoutSpaces.length() < word.length() && i + j < query.length()) {
        char c = query.charAt(i + j);
        candidate.append(c);
        if (c != ' ') candidateWithoutSpaces.append(c);
        j++;
    }
}

Output

[O HI T, HELL, H E L L, WE LC]