blob: e835235cd042a4b10931f6760ad19e13940bc063 [file] [log] [blame]
// Copyright 2016 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
import 'dart:math';
const List<String> _kWords = <String>[
/// A service that suggests words for a given input.
class WordSuggestionService {
/// Returns a list of words that are similar to [input].
List<String> suggestWords(String input) {
final List<String> suggestedWords = List<String>.from(_kWords)
..removeWhere((String a) => levenshteinDistance(input, a) > 3)
..sort((String a, String b) =>
levenshteinDistance(input, a) - levenshteinDistance(input, b));
return suggestedWords;
/// From
static int levenshteinDistance(String s, String t) {
// Degenerate cases.
if (s == t) {
return 0;
if (s.isEmpty) {
return t.length;
if (t.isEmpty) {
return s.length;
// Create two work vectors of integer distances.
final List<int> v0 = List<int>.filled(t.length + 1, 0);
final List<int> v1 = List<int>.filled(t.length + 1, 0);
// Initialize v0 (the previous row of distances).
// This row is A[0][i]: edit distance for an empty s.
// The distance is just the number of characters to delete from t.
for (int i = 0; i < v0.length; i++) {
v0[i] = i;
for (int i = 0; i < s.length; i++) {
// Calculate v1 (current row distances) from the previous row v0.
// First element of v1 is A[i+1][0].
// Edit distance is delete (i+1) chars from s to match empty t.
v1[0] = i + 1;
// Use formula to fill in the rest of the row.
for (int j = 0; j < t.length; j++) {
int cost = (s[i] == t[j]) ? 0 : 1;
v1[j + 1] = min(v1[j] + 1, min(v0[j + 1] + 1, v0[j] + cost));
// Copy v1 (current row) to v0 (previous row) for next iteration.
for (int j = 0; j < v0.length; j++) {
v0[j] = v1[j];
return v1[t.length];