लेवेंस्टीन दूरी
लेवेंस्टीन दूरी दो अनुक्रमों के बीच अंतर को मापने के लिए एक स्ट्रिंग मीट्रिक है। यह एक शब्द को दूसरे में बदलने के लिए आवश्यक एकल-वर्ण संपादन की न्यूनतम संख्या है।
उदाहरण के लिए -
विचार करें, हमारे पास ये दो स्ट्रिंग्स हैं -
const str1 = 'hitting';
const str2 = 'kitten';इन दो स्ट्रिंग्स के बीच लेवेंस्टीन दूरी 3 है क्योंकि हमें ये तीन संपादन करने होंगे -
- kitten → hitten ("k" के स्थान पर "h" का प्रतिस्थापन)
- hitten → hittin ("e" के स्थान पर "i" का प्रतिस्थापन)
- hittin → hitting (अंत में "g" का सम्मिलन)
हमें एक JavaScript फ़ंक्शन लिखना है जो दो स्ट्रिंग्स लेता है और उनके बीच लेवेंस्टीन दूरी की गणना करता है।
उदाहरण
निम्नलिखित कोड देखें:
const str1 = 'hitting';
const str2 = 'kitten';
const levenshteinDistance = (str1 = '', str2 = '') => {
const track = Array(str2.length + 1).fill(null).map(() =>
Array(str1.length + 1).fill(null)
);
for (let i = 0; i <= str1.length; i += 1) {
track[0][i] = i;
}
for (let j = 0; j <= str2.length; j += 1) {
track[j][0] = j;
}
for (let j = 1; j <= str2.length; j += 1) {
for (let i = 1; i <= str1.length; i += 1) {
const indicator = str1[i - 1] === str2[j - 1] ? 0 : 1;
track[j][i] = Math.min(
track[j][i - 1] + 1, // विलोपन
track[j - 1][i] + 1, // सम्मिलन
track[j - 1][i - 1] + indicator // प्रतिस्थापन
);
}
}
return track[str2.length][str1.length];
};
console.log(levenshteinDistance(str1, str2));आउटपुट
कंसोल पर निम्नलिखित आउटपुट प्राप्त होगा:
3
