Return the Levenshtein edit distance between two strings *a* and *b*.
(a: str, b: str)
| 127 | |
| 128 | |
| 129 | def levenshtein_distance(a: str, b: str) -> int: |
| 130 | """Return the Levenshtein edit distance between two strings *a* and *b*.""" |
| 131 | if a == b: |
| 132 | return 0 |
| 133 | if len(a) < len(b): |
| 134 | a, b = b, a |
| 135 | if not a: |
| 136 | return len(b) |
| 137 | previous_row = list(range(len(b) + 1)) |
| 138 | for i, column1 in enumerate(a): |
| 139 | current_row = [i + 1] |
| 140 | for j, column2 in enumerate(b): |
| 141 | insertions = previous_row[j + 1] + 1 |
| 142 | deletions = current_row[j] + 1 |
| 143 | substitutions = previous_row[j] + (column1 != column2) |
| 144 | current_row.append(min(insertions, deletions, substitutions)) |
| 145 | previous_row = current_row |
| 146 | return previous_row[-1] |
| 147 | |
| 148 | |
| 149 | class UIDTransform(SphinxTransform): |