| // Copyright 2023 The Chromium Authors | |
| // Use of this source code is governed by a BSD-style license that can be | |
| // found in the LICENSE file. | |
| #ifndef BASE_STRINGS_LEVENSHTEIN_DISTANCE_H_ | |
| #define BASE_STRINGS_LEVENSHTEIN_DISTANCE_H_ | |
| #include <stddef.h> | |
| #include <optional> | |
| #include <string_view> | |
| #include "polyfills/base/base_export.h" | |
| namespace gurl_base { | |
| // Returns the Levenshtein distance of `a` and `b`. Edits, inserts and removes | |
| // each count as one step. | |
| // If `k = max_distance` is provided, the distance is only correctly calculated | |
| // up to k. In case the actual Levenshtein distance is larger than k, k+1 is | |
| // returned instead. This is useful for checking whether the distance is at most | |
| // some small constant, since the algorithm is more efficient in this case. | |
| // Complexity: | |
| // - Without k: O(|a| * |b|) time and O(max(|a|, |b|)) memory. | |
| // - With k: O(min(|a|, |b|) * k + k) time and O(k) memory. | |
| BASE_EXPORT size_t | |
| LevenshteinDistance(std::string_view a, | |
| std::string_view b, | |
| std::optional<size_t> max_distance = std::nullopt); | |
| BASE_EXPORT size_t | |
| LevenshteinDistance(std::u16string_view a, | |
| std::u16string_view b, | |
| std::optional<size_t> max_distance = std::nullopt); | |
| } // namespace base | |
| #endif // BASE_STRINGS_LEVENSHTEIN_DISTANCE_H_ |