| 145 | } |
| 146 | |
| 147 | std::string::size_type editDistance(const std::string& str1, const std::string& str2) { |
| 148 | |
| 149 | using str_size_t = std::string::size_type; |
| 150 | |
| 151 | const auto str1_size = str1.size() + 1; |
| 152 | const auto str2_size = str2.size() + 1; |
| 153 | |
| 154 | auto distance = Matrix<str_size_t>(str1_size, str2_size); |
| 155 | |
| 156 | // Initialise zeroth column and row with string index |
| 157 | for (str_size_t i = 0; i < str1_size; ++i) { |
| 158 | distance(i, 0) = i; |
| 159 | } |
| 160 | for (str_size_t j = 0; j < str2_size; ++j) { |
| 161 | distance(0, j) = j; |
| 162 | } |
| 163 | |
| 164 | // Wikipedia uses 1-indexing for the input strings, but 0-indexing |
| 165 | // for the `d` matrix, so the input strings have an additional `-1` |
| 166 | // when indexing them |
| 167 | for (str_size_t i = 1; i < str1_size; ++i) { |
| 168 | for (str_size_t j = 1; j < str2_size; ++j) { |
| 169 | const str_size_t cost = (str1[i - 1] == str2[j - 1]) ? 0 : 1; |
| 170 | |
| 171 | distance(i, j) = std::min({ |
| 172 | distance(i - 1, j) + 1, // deletion |
| 173 | distance(i, j - 1) + 1, // insertion |
| 174 | distance(i - 1, j - 1) + cost // substitution |
| 175 | }); |
| 176 | |
| 177 | if (i > 1 and j > 1 and (str1[i - 1] == str2[j - 2]) |
| 178 | and (str1[i - 2] == str2[j - 1])) { |
| 179 | // transposition |
| 180 | distance(i, j) = std::min(distance(i, j), distance(i - 2, j - 2) + 1); |
| 181 | } |
| 182 | } |
| 183 | } |
| 184 | |
| 185 | return distance(str1_size - 1, str2_size - 1); |
| 186 | } |