Merge branch 'master' into libReferenceDirective

microsoft · rbuckton · May 11, 2017 · May 11, 2017 · May 12, 2017 · May 13, 2017
commit f1fe66e2f0d594f98363b6ba19a71a8569c1295f
diff --git a/src/compiler/utilities.ts b/src/compiler/utilities.ts
@@ -4309,6 +4309,29 @@ namespace ts {
         }
         return bestCandidate;
     }
+
+    export function levenshtein(s1: string, s2: string): number {
+        let previous: number[] = new Array(s2.length + 1);
+        let current: number[] = new Array(s2.length + 1);
+        for (let i = 0; i < s2.length + 1; i++) {
+            previous[i] = i;
+            current[i] = -1;
+        }
+        for (let i = 1; i < s1.length + 1; i++) {
+            current[0] = i;
+            for (let j = 1; j < s2.length + 1; j++) {
+                current[j] = Math.min(
+                    previous[j] + 1,
+                    current[j - 1] + 1,
+                    previous[j - 1] + (s1[i - 1] === s2[j - 1] ? 0 : 2));
+            }
+            // shift current back to previous, and then reuse previous' array
+            const tmp = previous;
+            previous = current;
+            current = tmp;
+        }
+        return previous[previous.length - 1];
+    }
 }
 
 namespace ts {