{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch1\u003eEdit Distance (Levenshtein Distance)\u003c/h1\u003e\n\u003cbr\u003e\n\n\u003cp\u003e\nFind the edit distance between given two words \u003cvar\u003es1\u003c/var\u003e and \u003cvar\u003es2\u003c/var\u003e.\n\u003c/p\u003e\n\n\u003cp\u003e\nThe disntace is the minimum number of single-character edits required to change one word into the other. The edits including the following operations:\n\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003e\u003cstrong\u003einsertion\u003c/strong\u003e: Insert a character at a particular position.\u003c/li\u003e\n\u003cli\u003e\u003cstrong\u003edeletion\u003c/strong\u003e: Delete a character at a particular position. \u003c/li\u003e\n\u003cli\u003e\u003cstrong\u003esubstitution\u003c/strong\u003e: Change the character at a particular position to a different character \u003c/li\u003e\n\u003c/ul\u003e\n\n\u003ch2\u003eInput\u003c/h2\u003e\n\n\u003cpre\u003e\u003cvar\u003es1\u003c/var\u003e\n\u003cvar\u003es2\u003c/var\u003e\n\u003c/pre\u003e\n\n\u003cp\u003e\nTwo words \u003cvar\u003es1\u003c/var\u003e and \u003cvar\u003es2\u003c/var\u003e are given in the first line and the second line respectively. The words will consist of lower case characters.\n\u003c/p\u003e\n\n\u003ch2\u003eOutput\u003c/h2\u003e\n\n\u003cp\u003e\nPrint the edit distance in a line.\n\u003c/p\u003e\n\n\u003ch2\u003eConstraints\u003c/h2\u003e\n\n\u003cul\u003e\n\u003cli\u003e1 ≤ length of \u003cvar\u003es1\u003c/var\u003e ≤ 1000\u003c/li\u003e\n\u003cli\u003e1 ≤ length of \u003cvar\u003es2\u003c/var\u003e ≤ 1000\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003ch2\u003eSample Input 1\u003c/h2\u003e\n\u003cpre\u003eacac\nacm\n\u003c/pre\u003e\n\u003ch2\u003eSample Output 1\u003c/h2\u003e\n\u003cpre\u003e2\n\u003c/pre\u003e\n\u003cbr\u003e\n\n\u003ch2\u003eSample Input 2\u003c/h2\u003e\n\u003cpre\u003eicpc\nicpc\n\u003c/pre\u003e\n\u003ch2\u003eSample Output 2\u003c/h2\u003e\n\u003cpre\u003e0\n\u003c/pre\u003e"}}]}