जावास्क्रिप्ट में लेवेनशेटिन दूरी

लेवेनशेटिन दूरी

लेवेनशेटिन दूरी दो अनुक्रमों के बीच अंतर को मापने के लिए एक स्ट्रिंग मीट्रिक है। यह एक शब्द को दूसरे में बदलने के लिए आवश्यक एकल-वर्ण संपादन की न्यूनतम संख्या है।

उदाहरण के लिए -

गौर कीजिए, हमारे पास ये दो तार हैं -

const str1 = 'hitting';
const str2 = 'kitten';

इन दो तारों के बीच लेवेनशेटिन की दूरी 3 है क्योंकि हमें ये तीन संपादन करने की आवश्यकता है -

• बिल्ली का बच्चा → हिटन ("के" के लिए "एच" का प्रतिस्थापन)

• हिटन → हिटिन ("ई" के लिए "i" का प्रतिस्थापन)

• हिटिन → हिटिंग (अंत में "g" डालें)

हमें एक जावास्क्रिप्ट फ़ंक्शन लिखना है जो दो स्ट्रिंग्स लेता है और उनके बीच लेवेनशेटिन दूरी की गणना करता है।

उदाहरण

निम्नलिखित कोड है -

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, // deletion
            track[j - 1][i] + 1, // insertion
            track[j - 1][i - 1] + indicator, // substitution
         );
      }
   }
   return track[str2.length][str1.length];
};
console.log(levenshteinDistance(str1, str2));

आउटपुट

कंसोल पर आउटपुट निम्न है -

3