eayurt
March 25, 2026, 10:36am
1
Hello
This week question is about implement a fuzzy string search. Here it is
Given a text string and a pattern, implement a fuzzy string search using the Bitap algorithm that finds all positions in the text where the pattern matches with at most k errors (insertions, deletions, or substitutions). Return an array of objects containing the position and the number of errors at that match.
> fuzzySearch("the cat sat on the mat", "cat", 0);
> [{ position: 4, errors: 0 }]
> fuzzySearch("cassidoo", "cool", 1);
> []
> fuzzySearch("cassidoo", "cool", 3);
> [{ "position": 3, "errors": 3 }, { "position": 4, "errors": 2 }]
Happy coding!
1 Like
lpogic
March 28, 2026, 8:25am
2
The last example looks broken to me again… I’m not sure if I used the Bitap algorithm in the solution below, but it works somehow, so I’m posting it:
Solution
def min_error haystack, haystack_left, needle, needle_left
return 0 if needle_left <= 0
return needle_left if haystack_left <= 0
substitution_error = min_error haystack, haystack_left - 1, needle, needle_left - 1
return substitution_error if haystack[-haystack_left] == needle[-needle_left]
1 + [
min_error(haystack, haystack_left, needle, needle_left - 1),
min_error(haystack, haystack_left - 1, needle, needle_left),
substitution_error
].min
end
def fuzzySearch haystack, needle, max_error
(0...haystack.size).filter_map do |i|
error = min_error haystack, haystack.size - i, needle, needle.size
{position: i, errors: error} if error <= max_error
end
end
p fuzzySearch("the cat sat on the mat", "cat", 0) # => [{position: 4, error: 0}]
p fuzzySearch("cassidoo", "cool", 1) # => []
p fuzzySearch("cassidoo", "cool", 3) # => [{position: 0, error: 3}, {position: 4, error: 3}, {position: 5, error: 2}, {position: 6, error: 2}, {position: 7, error: 3}]
