1 // Copyright 2023 The Chromium Authors 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef BASE_STRINGS_LEVENSHTEIN_DISTANCE_H_ 6 #define BASE_STRINGS_LEVENSHTEIN_DISTANCE_H_ 7 8 #include <stddef.h> 9 10 #include <optional> 11 #include <string_view> 12 13 #include "base/base_export.h" 14 15 namespace base { 16 17 // Returns the Levenshtein distance of `a` and `b`. Edits, inserts and removes 18 // each count as one step. 19 // If `k = max_distance` is provided, the distance is only correctly calculated 20 // up to k. In case the actual Levenshtein distance is larger than k, k+1 is 21 // returned instead. This is useful for checking whether the distance is at most 22 // some small constant, since the algorithm is more efficient in this case. 23 // Complexity: 24 // - Without k: O(|a| * |b|) time and O(max(|a|, |b|)) memory. 25 // - With k: O(min(|a|, |b|) * k + k) time and O(k) memory. 26 BASE_EXPORT size_t 27 LevenshteinDistance(std::string_view a, 28 std::string_view b, 29 std::optional<size_t> max_distance = std::nullopt); 30 BASE_EXPORT size_t 31 LevenshteinDistance(std::u16string_view a, 32 std::u16string_view b, 33 std::optional<size_t> max_distance = std::nullopt); 34 35 } // namespace base 36 37 #endif // BASE_STRINGS_LEVENSHTEIN_DISTANCE_H_ 38