{"group":{"id":1,"name":"Community","lockable":false,"created_at":"2012-01-18T18:02:15.000Z","updated_at":"2026-04-06T14:01:22.000Z","description":"Problems submitted by members of the MATLAB Central community.","is_default":true,"created_by":161519,"badge_id":null,"featured":false,"trending":false,"solution_count_in_trending_period":0,"trending_last_calculated":"2026-04-06T00:00:00.000Z","image_id":null,"published":true,"community_created":false,"status_id":2,"is_default_group_for_player":false,"deleted_by":null,"deleted_at":null,"restored_by":null,"restored_at":null,"description_opc":null,"description_html":null,"published_at":null},"problems":[{"id":2523,"title":"longest common substring : Skipped character version","description":"Two strings are given. Find the longest common substring between them. The substring characters need not be adjacent. They, however, must appear in same order in both input strings.\r\n\r\nExample:\r\n\r\n  str1 = 'abcdefghi';\r\n  str2 = 'zazbzczd';\r\n  \r\n  output = 'abcd'","description_html":"\u003cp\u003eTwo strings are given. Find the longest common substring between them. The substring characters need not be adjacent. They, however, must appear in same order in both input strings.\u003c/p\u003e\u003cp\u003eExample:\u003c/p\u003e\u003cpre class=\"language-matlab\"\u003estr1 = 'abcdefghi';\r\nstr2 = 'zazbzczd';\r\n\u003c/pre\u003e\u003cpre class=\"language-matlab\"\u003eoutput = 'abcd'\r\n\u003c/pre\u003e","function_template":"function y = skipped(str1,str2)\r\n  y = x;\r\nend","test_suite":"%%\r\nstr1 = 'abcdefghi';\r\nstr2 = 'zazbzczd';\r\ny_correct = 'abcd';\r\nassert(isequal(skipped(str1,str2),y_correct))\r\n\r\n%%\r\nstr1 = 'abcdefghi';\r\nstr2 = 'zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz';\r\ny_correct = '';\r\nassert(isequal(skipped(str1,str2),y_correct))\r\n\r\n\r\n\r\n%%\r\nstr1 = 'catcatcat';\r\nstr2 = 'catcatcat';\r\ny_correct = str1;\r\nassert(isequal(skipped(str1,str2),y_correct))\r\n\r\n\r\n%%\r\nstr1 = 'an example of a string';\r\nstr2 = 'the example z a s t r i i i n ssss';\r\ny_correct = ' example  a strin';\r\nassert(isequal(skipped(str1,str2),y_correct))\r\n\r\n\r\n%%\r\nstr1 = 'a string with many characters';\r\nstr2 = 'zzz zzz zzz zzz zzz';\r\ny_correct = '    ';\r\nassert(isequal(skipped(str1,str2),y_correct))\r\n\r\n\r\n%%\r\nstr1 = 'lets!not!use!spaces';\r\nstr2 = 'z!zzzzzzzzZZZzZzZ!zzzzz!zzzzzzzzz!!!!!!!!!zzz';\r\ny_correct = '!!!';\r\nassert(isequal(skipped(str1,str2),y_correct))","published":true,"deleted":false,"likes_count":0,"comments_count":4,"created_by":17203,"edited_by":null,"edited_at":null,"deleted_by":null,"deleted_at":null,"solvers_count":53,"test_suite_updated_at":null,"rescore_all_solutions":false,"group_id":32,"created_at":"2014-08-20T10:44:21.000Z","updated_at":"2026-04-08T08:28:14.000Z","published_at":"2014-08-20T10:44:21.000Z","restored_at":null,"restored_by":null,"spam":false,"simulink":false,"admin_reviewed":false,"description_opc":"{\"relationships\":[{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/document\",\"targetMode\":\"\",\"relationshipId\":\"rId1\",\"target\":\"/matlab/document.xml\"},{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/output\",\"targetMode\":\"\",\"relationshipId\":\"rId2\",\"target\":\"/matlab/output.xml\"}],\"parts\":[{\"partUri\":\"/matlab/document.xml\",\"relationship\":[],\"contentType\":\"application/vnd.mathworks.matlab.code.document+xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\"?\u003e\\n\u003cw:document xmlns:w=\\\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\\\"\u003e\u003cw:body\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eTwo strings are given. Find the longest common substring between them. The substring characters need not be adjacent. They, however, must appear in same order in both input strings.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eExample:\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[str1 = 'abcdefghi';\\nstr2 = 'zazbzczd';\\n\\noutput = 'abcd']]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003c/w:body\u003e\u003c/w:document\u003e\"},{\"partUri\":\"/matlab/output.xml\",\"contentType\":\"text/xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\" standalone=\\\"no\\\" ?\u003e\u003cembeddedOutputs\u003e\u003cmetaData\u003e\u003cevaluationState\u003emanual\u003c/evaluationState\u003e\u003clayoutState\u003ecode\u003c/layoutState\u003e\u003coutputStatus\u003eready\u003c/outputStatus\u003e\u003c/metaData\u003e\u003coutputArray type=\\\"array\\\"/\u003e\u003cregionArray type=\\\"array\\\"/\u003e\u003c/embeddedOutputs\u003e\"}]}"},{"id":2309,"title":"Calculate the Damerau-Levenshtein distance between two strings.","description":"\u003chttp://www.mathworks.co.uk/matlabcentral/cody/problems/2303-compute-hamming-distances-between-each-pair-of-rows-from-two-input-matrices Problem 2303\u003e reminded me a few older ones dealing with metrics between strings, problems \u003chttp://www.mathworks.co.uk/matlabcentral/cody/problems/93-calculate-the-levenshtein-distance-between-two-strings 93\u003e,\r\n\u003chttp://www.mathworks.co.uk/matlabcentral/cody/problems/846-calculate-the-hamming-distance-between-two-strings 846\u003e or\r\n\u003chttp://www.mathworks.co.uk/matlabcentral/cody/problems/848-calculate-a-modified-levenshtein-distance-between-two-strings 848\u003e\r\n about Hamming and Levenshtein distances.\r\n\r\n\u003chttp://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance Damerau-Levenshtein distance\u003e is an extension to Levenshtein distance. It is also defined as minimum number of simple edit operations on string to change it into another, but the list of allowed operations is extended.\r\n\r\nAs it is written on Wikipedia there are 4 allowed edits: deletion, insertion and substitution of an single character and an transposition of two adjacent characters.\r\n\r\nExample. Such defined distance between words _gifts_ and _profit_ is 5:\r\n\r\n  gifts   =\u003e pgifts    (insertion of 'p')\r\n  pgifts  =\u003e prgifts   (insertion of 'r')\r\n  prgifts =\u003e proifts   (substitution of 'g' to 'o')\r\n  proifts =\u003e profits   (transposition of 'if' to 'fi')\r\n  profits =\u003e profit    (deletion of 's')\r\n  \r\n\r\n","description_html":"\u003cp\u003e\u003ca href = \"http://www.mathworks.co.uk/matlabcentral/cody/problems/2303-compute-hamming-distances-between-each-pair-of-rows-from-two-input-matrices\"\u003eProblem 2303\u003c/a\u003e reminded me a few older ones dealing with metrics between strings, problems \u003ca href = \"http://www.mathworks.co.uk/matlabcentral/cody/problems/93-calculate-the-levenshtein-distance-between-two-strings\"\u003e93\u003c/a\u003e, \u003ca href = \"http://www.mathworks.co.uk/matlabcentral/cody/problems/846-calculate-the-hamming-distance-between-two-strings\"\u003e846\u003c/a\u003e or \u003ca href = \"http://www.mathworks.co.uk/matlabcentral/cody/problems/848-calculate-a-modified-levenshtein-distance-between-two-strings\"\u003e848\u003c/a\u003e\r\n about Hamming and Levenshtein distances.\u003c/p\u003e\u003cp\u003e\u003ca href = \"http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance\"\u003eDamerau-Levenshtein distance\u003c/a\u003e is an extension to Levenshtein distance. It is also defined as minimum number of simple edit operations on string to change it into another, but the list of allowed operations is extended.\u003c/p\u003e\u003cp\u003eAs it is written on Wikipedia there are 4 allowed edits: deletion, insertion and substitution of an single character and an transposition of two adjacent characters.\u003c/p\u003e\u003cp\u003eExample. Such defined distance between words \u003ci\u003egifts\u003c/i\u003e and \u003ci\u003eprofit\u003c/i\u003e is 5:\u003c/p\u003e\u003cpre class=\"language-matlab\"\u003egifts   =\u0026gt; pgifts    (insertion of 'p')\r\npgifts  =\u0026gt; prgifts   (insertion of 'r')\r\nprgifts =\u0026gt; proifts   (substitution of 'g' to 'o')\r\nproifts =\u0026gt; profits   (transposition of 'if' to 'fi')\r\nprofits =\u0026gt; profit    (deletion of 's')\r\n\u003c/pre\u003e","function_template":"function distance = Damerau_Levenshtein(str1,str2)\r\n  distance = 0;\r\nend","test_suite":"%%\r\nassert(isequal(Damerau_Levenshtein('mom','dad'),3));\r\n% 3 substitutions\r\n%%\r\nassert(isequal(Damerau_Levenshtein('dogs','dog'),1));\r\n% 1 deletion\r\n%%\r\nassert(isequal(Damerau_Levenshtein('true','true'),0));\r\n% identity\r\n%%\r\nassert(isequal(Damerau_Levenshtein('true','false'),4));\r\n% 1 insertion, 3 substitutions\r\n%%\r\nassert(isequal(Damerau_Levenshtein('abc','ca'),2));\r\n% 1 deletion, 1 transposition\r\n%%\r\nassert(isequal(Damerau_Levenshtein('tee','tree'),1));\r\n%%\r\nassert(isequal(Damerau_Levenshtein('email','mails'),2));\r\n%%\r\nassert(isequal(Damerau_Levenshtein('profit','gifts'),5));\r\n%%\r\n% symmetry\r\nrnd=@()char(randi([97 122],1,randi([4 10])));\r\nfor k=1:10\r\n  str1=rnd();\r\n  str2=rnd();\r\n  a=Damerau_Levenshtein(str1,str2);\r\n  b=Damerau_Levenshtein(str2,str1);\r\n  assert(isequal(a,b))\r\nend\r\n%%\r\n% trinagle inequality\r\nrnd=@()char(randi([97 122],1,randi([4 10])));\r\nfor k=1:50\r\n  str1=rnd();\r\n  str2=rnd();\r\n  str3=rnd();\r\n  a=Damerau_Levenshtein(str2,str3);\r\n  b=Damerau_Levenshtein(str3,str1);\r\n  c=Damerau_Levenshtein(str1,str2);\r\n  assert(a+b\u003e=c)\r\nend","published":true,"deleted":false,"likes_count":1,"comments_count":8,"created_by":14358,"edited_by":null,"edited_at":null,"deleted_by":null,"deleted_at":null,"solvers_count":46,"test_suite_updated_at":"2014-05-07T12:40:15.000Z","rescore_all_solutions":false,"group_id":32,"created_at":"2014-05-07T12:34:17.000Z","updated_at":"2026-04-08T09:10:54.000Z","published_at":"2014-05-07T12:40:15.000Z","restored_at":null,"restored_by":null,"spam":false,"simulink":false,"admin_reviewed":false,"description_opc":"{\"relationships\":[{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/document\",\"targetMode\":\"\",\"relationshipId\":\"rId1\",\"target\":\"/matlab/document.xml\"},{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/output\",\"targetMode\":\"\",\"relationshipId\":\"rId2\",\"target\":\"/matlab/output.xml\"}],\"parts\":[{\"partUri\":\"/matlab/document.xml\",\"relationship\":[],\"contentType\":\"application/vnd.mathworks.matlab.code.document+xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\"?\u003e\\n\u003cw:document xmlns:w=\\\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\\\"\u003e\u003cw:body\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:hyperlink w:docLocation=\\\"http://www.mathworks.co.uk/matlabcentral/cody/problems/2303-compute-hamming-distances-between-each-pair-of-rows-from-two-input-matrices\\\"\u003e\u003cw:r\u003e\u003cw:t\u003eProblem 2303\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e reminded me a few older ones dealing with metrics between strings, problems\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"http://www.mathworks.co.uk/matlabcentral/cody/problems/93-calculate-the-levenshtein-distance-between-two-strings\\\"\u003e\u003cw:r\u003e\u003cw:t\u003e93\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e,\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"http://www.mathworks.co.uk/matlabcentral/cody/problems/846-calculate-the-hamming-distance-between-two-strings\\\"\u003e\u003cw:r\u003e\u003cw:t\u003e846\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e or\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"http://www.mathworks.co.uk/matlabcentral/cody/problems/848-calculate-a-modified-levenshtein-distance-between-two-strings\\\"\u003e\u003cw:r\u003e\u003cw:t\u003e848\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e about Hamming and Levenshtein distances.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:hyperlink w:docLocation=\\\"http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance\\\"\u003e\u003cw:r\u003e\u003cw:t\u003eDamerau-Levenshtein distance\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e is an extension to Levenshtein distance. It is also defined as minimum number of simple edit operations on string to change it into another, but the list of allowed operations is extended.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eAs it is written on Wikipedia there are 4 allowed edits: deletion, insertion and substitution of an single character and an transposition of two adjacent characters.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eExample. Such defined distance between words\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003egifts\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e and\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eprofit\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e is 5:\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[gifts   =\u003e pgifts    (insertion of 'p')\\npgifts  =\u003e prgifts   (insertion of 'r')\\nprgifts =\u003e proifts   (substitution of 'g' to 'o')\\nproifts =\u003e profits   (transposition of 'if' to 'fi')\\nprofits =\u003e profit    (deletion of 's')]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003c/w:body\u003e\u003c/w:document\u003e\"},{\"partUri\":\"/matlab/output.xml\",\"contentType\":\"text/xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\" standalone=\\\"no\\\" ?\u003e\u003cembeddedOutputs\u003e\u003cmetaData\u003e\u003cevaluationState\u003emanual\u003c/evaluationState\u003e\u003clayoutState\u003ecode\u003c/layoutState\u003e\u003coutputStatus\u003eready\u003c/outputStatus\u003e\u003c/metaData\u003e\u003coutputArray type=\\\"array\\\"/\u003e\u003cregionArray type=\\\"array\\\"/\u003e\u003c/embeddedOutputs\u003e\"}]}"}],"problem_search":{"errors":[],"problems":[{"id":2523,"title":"longest common substring : Skipped character version","description":"Two strings are given. Find the longest common substring between them. The substring characters need not be adjacent. They, however, must appear in same order in both input strings.\r\n\r\nExample:\r\n\r\n  str1 = 'abcdefghi';\r\n  str2 = 'zazbzczd';\r\n  \r\n  output = 'abcd'","description_html":"\u003cp\u003eTwo strings are given. Find the longest common substring between them. The substring characters need not be adjacent. They, however, must appear in same order in both input strings.\u003c/p\u003e\u003cp\u003eExample:\u003c/p\u003e\u003cpre class=\"language-matlab\"\u003estr1 = 'abcdefghi';\r\nstr2 = 'zazbzczd';\r\n\u003c/pre\u003e\u003cpre class=\"language-matlab\"\u003eoutput = 'abcd'\r\n\u003c/pre\u003e","function_template":"function y = skipped(str1,str2)\r\n  y = x;\r\nend","test_suite":"%%\r\nstr1 = 'abcdefghi';\r\nstr2 = 'zazbzczd';\r\ny_correct = 'abcd';\r\nassert(isequal(skipped(str1,str2),y_correct))\r\n\r\n%%\r\nstr1 = 'abcdefghi';\r\nstr2 = 'zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz';\r\ny_correct = '';\r\nassert(isequal(skipped(str1,str2),y_correct))\r\n\r\n\r\n\r\n%%\r\nstr1 = 'catcatcat';\r\nstr2 = 'catcatcat';\r\ny_correct = str1;\r\nassert(isequal(skipped(str1,str2),y_correct))\r\n\r\n\r\n%%\r\nstr1 = 'an example of a string';\r\nstr2 = 'the example z a s t r i i i n ssss';\r\ny_correct = ' example  a strin';\r\nassert(isequal(skipped(str1,str2),y_correct))\r\n\r\n\r\n%%\r\nstr1 = 'a string with many characters';\r\nstr2 = 'zzz zzz zzz zzz zzz';\r\ny_correct = '    ';\r\nassert(isequal(skipped(str1,str2),y_correct))\r\n\r\n\r\n%%\r\nstr1 = 'lets!not!use!spaces';\r\nstr2 = 'z!zzzzzzzzZZZzZzZ!zzzzz!zzzzzzzzz!!!!!!!!!zzz';\r\ny_correct = '!!!';\r\nassert(isequal(skipped(str1,str2),y_correct))","published":true,"deleted":false,"likes_count":0,"comments_count":4,"created_by":17203,"edited_by":null,"edited_at":null,"deleted_by":null,"deleted_at":null,"solvers_count":53,"test_suite_updated_at":null,"rescore_all_solutions":false,"group_id":32,"created_at":"2014-08-20T10:44:21.000Z","updated_at":"2026-04-08T08:28:14.000Z","published_at":"2014-08-20T10:44:21.000Z","restored_at":null,"restored_by":null,"spam":false,"simulink":false,"admin_reviewed":false,"description_opc":"{\"relationships\":[{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/document\",\"targetMode\":\"\",\"relationshipId\":\"rId1\",\"target\":\"/matlab/document.xml\"},{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/output\",\"targetMode\":\"\",\"relationshipId\":\"rId2\",\"target\":\"/matlab/output.xml\"}],\"parts\":[{\"partUri\":\"/matlab/document.xml\",\"relationship\":[],\"contentType\":\"application/vnd.mathworks.matlab.code.document+xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\"?\u003e\\n\u003cw:document xmlns:w=\\\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\\\"\u003e\u003cw:body\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eTwo strings are given. Find the longest common substring between them. The substring characters need not be adjacent. They, however, must appear in same order in both input strings.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eExample:\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[str1 = 'abcdefghi';\\nstr2 = 'zazbzczd';\\n\\noutput = 'abcd']]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003c/w:body\u003e\u003c/w:document\u003e\"},{\"partUri\":\"/matlab/output.xml\",\"contentType\":\"text/xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\" standalone=\\\"no\\\" ?\u003e\u003cembeddedOutputs\u003e\u003cmetaData\u003e\u003cevaluationState\u003emanual\u003c/evaluationState\u003e\u003clayoutState\u003ecode\u003c/layoutState\u003e\u003coutputStatus\u003eready\u003c/outputStatus\u003e\u003c/metaData\u003e\u003coutputArray type=\\\"array\\\"/\u003e\u003cregionArray type=\\\"array\\\"/\u003e\u003c/embeddedOutputs\u003e\"}]}"},{"id":2309,"title":"Calculate the Damerau-Levenshtein distance between two strings.","description":"\u003chttp://www.mathworks.co.uk/matlabcentral/cody/problems/2303-compute-hamming-distances-between-each-pair-of-rows-from-two-input-matrices Problem 2303\u003e reminded me a few older ones dealing with metrics between strings, problems \u003chttp://www.mathworks.co.uk/matlabcentral/cody/problems/93-calculate-the-levenshtein-distance-between-two-strings 93\u003e,\r\n\u003chttp://www.mathworks.co.uk/matlabcentral/cody/problems/846-calculate-the-hamming-distance-between-two-strings 846\u003e or\r\n\u003chttp://www.mathworks.co.uk/matlabcentral/cody/problems/848-calculate-a-modified-levenshtein-distance-between-two-strings 848\u003e\r\n about Hamming and Levenshtein distances.\r\n\r\n\u003chttp://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance Damerau-Levenshtein distance\u003e is an extension to Levenshtein distance. It is also defined as minimum number of simple edit operations on string to change it into another, but the list of allowed operations is extended.\r\n\r\nAs it is written on Wikipedia there are 4 allowed edits: deletion, insertion and substitution of an single character and an transposition of two adjacent characters.\r\n\r\nExample. Such defined distance between words _gifts_ and _profit_ is 5:\r\n\r\n  gifts   =\u003e pgifts    (insertion of 'p')\r\n  pgifts  =\u003e prgifts   (insertion of 'r')\r\n  prgifts =\u003e proifts   (substitution of 'g' to 'o')\r\n  proifts =\u003e profits   (transposition of 'if' to 'fi')\r\n  profits =\u003e profit    (deletion of 's')\r\n  \r\n\r\n","description_html":"\u003cp\u003e\u003ca href = \"http://www.mathworks.co.uk/matlabcentral/cody/problems/2303-compute-hamming-distances-between-each-pair-of-rows-from-two-input-matrices\"\u003eProblem 2303\u003c/a\u003e reminded me a few older ones dealing with metrics between strings, problems \u003ca href = \"http://www.mathworks.co.uk/matlabcentral/cody/problems/93-calculate-the-levenshtein-distance-between-two-strings\"\u003e93\u003c/a\u003e, \u003ca href = \"http://www.mathworks.co.uk/matlabcentral/cody/problems/846-calculate-the-hamming-distance-between-two-strings\"\u003e846\u003c/a\u003e or \u003ca href = \"http://www.mathworks.co.uk/matlabcentral/cody/problems/848-calculate-a-modified-levenshtein-distance-between-two-strings\"\u003e848\u003c/a\u003e\r\n about Hamming and Levenshtein distances.\u003c/p\u003e\u003cp\u003e\u003ca href = \"http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance\"\u003eDamerau-Levenshtein distance\u003c/a\u003e is an extension to Levenshtein distance. It is also defined as minimum number of simple edit operations on string to change it into another, but the list of allowed operations is extended.\u003c/p\u003e\u003cp\u003eAs it is written on Wikipedia there are 4 allowed edits: deletion, insertion and substitution of an single character and an transposition of two adjacent characters.\u003c/p\u003e\u003cp\u003eExample. Such defined distance between words \u003ci\u003egifts\u003c/i\u003e and \u003ci\u003eprofit\u003c/i\u003e is 5:\u003c/p\u003e\u003cpre class=\"language-matlab\"\u003egifts   =\u0026gt; pgifts    (insertion of 'p')\r\npgifts  =\u0026gt; prgifts   (insertion of 'r')\r\nprgifts =\u0026gt; proifts   (substitution of 'g' to 'o')\r\nproifts =\u0026gt; profits   (transposition of 'if' to 'fi')\r\nprofits =\u0026gt; profit    (deletion of 's')\r\n\u003c/pre\u003e","function_template":"function distance = Damerau_Levenshtein(str1,str2)\r\n  distance = 0;\r\nend","test_suite":"%%\r\nassert(isequal(Damerau_Levenshtein('mom','dad'),3));\r\n% 3 substitutions\r\n%%\r\nassert(isequal(Damerau_Levenshtein('dogs','dog'),1));\r\n% 1 deletion\r\n%%\r\nassert(isequal(Damerau_Levenshtein('true','true'),0));\r\n% identity\r\n%%\r\nassert(isequal(Damerau_Levenshtein('true','false'),4));\r\n% 1 insertion, 3 substitutions\r\n%%\r\nassert(isequal(Damerau_Levenshtein('abc','ca'),2));\r\n% 1 deletion, 1 transposition\r\n%%\r\nassert(isequal(Damerau_Levenshtein('tee','tree'),1));\r\n%%\r\nassert(isequal(Damerau_Levenshtein('email','mails'),2));\r\n%%\r\nassert(isequal(Damerau_Levenshtein('profit','gifts'),5));\r\n%%\r\n% symmetry\r\nrnd=@()char(randi([97 122],1,randi([4 10])));\r\nfor k=1:10\r\n  str1=rnd();\r\n  str2=rnd();\r\n  a=Damerau_Levenshtein(str1,str2);\r\n  b=Damerau_Levenshtein(str2,str1);\r\n  assert(isequal(a,b))\r\nend\r\n%%\r\n% trinagle inequality\r\nrnd=@()char(randi([97 122],1,randi([4 10])));\r\nfor k=1:50\r\n  str1=rnd();\r\n  str2=rnd();\r\n  str3=rnd();\r\n  a=Damerau_Levenshtein(str2,str3);\r\n  b=Damerau_Levenshtein(str3,str1);\r\n  c=Damerau_Levenshtein(str1,str2);\r\n  assert(a+b\u003e=c)\r\nend","published":true,"deleted":false,"likes_count":1,"comments_count":8,"created_by":14358,"edited_by":null,"edited_at":null,"deleted_by":null,"deleted_at":null,"solvers_count":46,"test_suite_updated_at":"2014-05-07T12:40:15.000Z","rescore_all_solutions":false,"group_id":32,"created_at":"2014-05-07T12:34:17.000Z","updated_at":"2026-04-08T09:10:54.000Z","published_at":"2014-05-07T12:40:15.000Z","restored_at":null,"restored_by":null,"spam":false,"simulink":false,"admin_reviewed":false,"description_opc":"{\"relationships\":[{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/document\",\"targetMode\":\"\",\"relationshipId\":\"rId1\",\"target\":\"/matlab/document.xml\"},{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/output\",\"targetMode\":\"\",\"relationshipId\":\"rId2\",\"target\":\"/matlab/output.xml\"}],\"parts\":[{\"partUri\":\"/matlab/document.xml\",\"relationship\":[],\"contentType\":\"application/vnd.mathworks.matlab.code.document+xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\"?\u003e\\n\u003cw:document xmlns:w=\\\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\\\"\u003e\u003cw:body\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:hyperlink w:docLocation=\\\"http://www.mathworks.co.uk/matlabcentral/cody/problems/2303-compute-hamming-distances-between-each-pair-of-rows-from-two-input-matrices\\\"\u003e\u003cw:r\u003e\u003cw:t\u003eProblem 2303\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e reminded me a few older ones dealing with metrics between strings, problems\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"http://www.mathworks.co.uk/matlabcentral/cody/problems/93-calculate-the-levenshtein-distance-between-two-strings\\\"\u003e\u003cw:r\u003e\u003cw:t\u003e93\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e,\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"http://www.mathworks.co.uk/matlabcentral/cody/problems/846-calculate-the-hamming-distance-between-two-strings\\\"\u003e\u003cw:r\u003e\u003cw:t\u003e846\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e or\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"http://www.mathworks.co.uk/matlabcentral/cody/problems/848-calculate-a-modified-levenshtein-distance-between-two-strings\\\"\u003e\u003cw:r\u003e\u003cw:t\u003e848\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e about Hamming and Levenshtein distances.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:hyperlink w:docLocation=\\\"http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance\\\"\u003e\u003cw:r\u003e\u003cw:t\u003eDamerau-Levenshtein distance\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e is an extension to Levenshtein distance. It is also defined as minimum number of simple edit operations on string to change it into another, but the list of allowed operations is extended.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eAs it is written on Wikipedia there are 4 allowed edits: deletion, insertion and substitution of an single character and an transposition of two adjacent characters.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eExample. Such defined distance between words\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003egifts\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e and\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eprofit\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e is 5:\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[gifts   =\u003e pgifts    (insertion of 'p')\\npgifts  =\u003e prgifts   (insertion of 'r')\\nprgifts =\u003e proifts   (substitution of 'g' to 'o')\\nproifts =\u003e profits   (transposition of 'if' to 'fi')\\nprofits =\u003e profit    (deletion of 's')]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003c/w:body\u003e\u003c/w:document\u003e\"},{\"partUri\":\"/matlab/output.xml\",\"contentType\":\"text/xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\" standalone=\\\"no\\\" ?\u003e\u003cembeddedOutputs\u003e\u003cmetaData\u003e\u003cevaluationState\u003emanual\u003c/evaluationState\u003e\u003clayoutState\u003ecode\u003c/layoutState\u003e\u003coutputStatus\u003eready\u003c/outputStatus\u003e\u003c/metaData\u003e\u003coutputArray type=\\\"array\\\"/\u003e\u003cregionArray type=\\\"array\\\"/\u003e\u003c/embeddedOutputs\u003e\"}]}"}],"term":"group:\"Strings III\" group:\"Algorithm I\"","current_player_id":null,"fields":[{"name":"page","type":"integer","callback":null,"default":1,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":null,"prepend":true},{"name":"per_page","type":"integer","callback":null,"default":50,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":null,"prepend":true},{"name":"sort","type":"string","callback":null,"default":null,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":null,"prepend":true},{"name":"body","type":"text","callback":null,"default":"*:*","directive":null,"facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":false},{"name":"group","type":"string","callback":null,"default":null,"directive":"group","facet":true,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"difficulty_rating_bin","type":"string","callback":null,"default":null,"directive":"difficulty_rating_bin","facet":true,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"id","type":"integer","callback":null,"default":null,"directive":"id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"tag","type":"string","callback":null,"default":null,"directive":"tag","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"product","type":"string","callback":null,"default":null,"directive":"product","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"created_at","type":"timeframe","callback":{},"default":null,"directive":"created_at","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"profile_id","type":"integer","callback":null,"default":null,"directive":"author_id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"created_by","type":"string","callback":null,"default":null,"directive":"author","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"player_id","type":"integer","callback":null,"default":null,"directive":"solver_id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"player","type":"string","callback":null,"default":null,"directive":"solver","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"solvers_count","type":"integer","callback":null,"default":null,"directive":"solvers_count","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"comments_count","type":"integer","callback":null,"default":null,"directive":"comments_count","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"likes_count","type":"integer","callback":null,"default":null,"directive":"likes_count","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"leader_id","type":"integer","callback":null,"default":null,"directive":"leader_id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"leading_solution","type":"integer","callback":null,"default":null,"directive":"leading_solution","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true}],"filters":[{"name":"asset_type","type":"string","callback":null,"default":null,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":"\"cody:problem\"","prepend":true},{"name":"profile_id","type":"integer","callback":{},"default":null,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":"author_id","static":null,"prepend":true}],"query":{"params":{"per_page":50,"term":"group:\"Strings III\" group:\"Algorithm I\"","current_player":null,"sort":"map(difficulty_value,0,0,999) asc"},"parser":"MathWorks::Search::Solr::QueryParser","directives":{"term":{"directives":{"group":[["group:\"Strings III\"","","\"","Strings III","\""],["group:\"Algorithm I\"","","\"","Algorithm I","\""]]}}},"facets":{"#\u003cMathWorks::Search::Field:0x00007f2473fff8e0\u003e":["Strings III","Algorithm I"],"#\u003cMathWorks::Search::Field:0x00007f2473fff840\u003e":null},"filters":{"#\u003cMathWorks::Search::Field:0x00007f2473ffd9a0\u003e":"\"cody:problem\""},"fields":{"#\u003cMathWorks::Search::Field:0x00007f2473fe0328\u003e":1,"#\u003cMathWorks::Search::Field:0x00007f2473fe01e8\u003e":50,"#\u003cMathWorks::Search::Field:0x00007f2473ffff20\u003e":"map(difficulty_value,0,0,999) asc","#\u003cMathWorks::Search::Field:0x00007f2473fffe80\u003e":"group:\"Strings III\" group:\"Algorithm I\""},"user_query":{"#\u003cMathWorks::Search::Field:0x00007f2473fffe80\u003e":"group:\"Strings III\" group:\"Algorithm I\""},"queried_facets":{"#\u003cMathWorks::Search::Field:0x00007f2473fff8e0\u003e":["Strings III","Algorithm I"]}},"query_backend":{"connection":{"configuration":{"index_url":"http://index-op-v2/solr/","query_url":"http://search-op-v2/solr/","direct_access_index_urls":["http://index-op-v2/solr/"],"direct_access_query_urls":["http://search-op-v2/solr/"],"timeout":10,"vhost":"search","exchange":"search.topic","heartbeat":30,"pre_index_mode":false,"host":"rabbitmq-eks","port":5672,"username":"cody-search","password":"78X075ddcV44","virtual_host":"search","indexer":"amqp","http_logging":"true","core":"cody"},"query_connection":{"uri":"http://search-op-v2/solr/cody/","proxy":null,"connection":{"parallel_manager":null,"headers":{"User-Agent":"Faraday v1.0.1"},"params":{},"options":{"params_encoder":"Faraday::FlatParamsEncoder","proxy":null,"bind":null,"timeout":null,"open_timeout":null,"read_timeout":null,"write_timeout":null,"boundary":null,"oauth":null,"context":null,"on_data":null},"ssl":{"verify":true,"ca_file":null,"ca_path":null,"verify_mode":null,"cert_store":null,"client_cert":null,"client_key":null,"certificate":null,"private_key":null,"verify_depth":null,"version":null,"min_version":null,"max_version":null},"default_parallel_manager":null,"builder":{"adapter":{"name":"Faraday::Adapter::NetHttp","args":[],"block":null},"handlers":[{"name":"Faraday::Response::RaiseError","args":[],"block":null}],"app":{"app":{"ssl_cert_store":{"verify_callback":null,"error":null,"error_string":null,"chain":null,"time":null},"app":{},"connection_options":{},"config_block":null}}},"url_prefix":"http://search-op-v2/solr/cody/","manual_proxy":false,"proxy":null},"update_format":"RSolr::JSON::Generator","update_path":"update","options":{"url":"http://search-op-v2/solr/cody"}}},"query":{"params":{"per_page":50,"term":"group:\"Strings III\" group:\"Algorithm I\"","current_player":null,"sort":"map(difficulty_value,0,0,999) asc"},"parser":"MathWorks::Search::Solr::QueryParser","directives":{"term":{"directives":{"group":[["group:\"Strings III\"","","\"","Strings III","\""],["group:\"Algorithm I\"","","\"","Algorithm I","\""]]}}},"facets":{"#\u003cMathWorks::Search::Field:0x00007f2473fff8e0\u003e":["Strings III","Algorithm I"],"#\u003cMathWorks::Search::Field:0x00007f2473fff840\u003e":null},"filters":{"#\u003cMathWorks::Search::Field:0x00007f2473ffd9a0\u003e":"\"cody:problem\""},"fields":{"#\u003cMathWorks::Search::Field:0x00007f2473fe0328\u003e":1,"#\u003cMathWorks::Search::Field:0x00007f2473fe01e8\u003e":50,"#\u003cMathWorks::Search::Field:0x00007f2473ffff20\u003e":"map(difficulty_value,0,0,999) asc","#\u003cMathWorks::Search::Field:0x00007f2473fffe80\u003e":"group:\"Strings III\" group:\"Algorithm I\""},"user_query":{"#\u003cMathWorks::Search::Field:0x00007f2473fffe80\u003e":"group:\"Strings III\" group:\"Algorithm I\""},"queried_facets":{"#\u003cMathWorks::Search::Field:0x00007f2473fff8e0\u003e":["Strings III","Algorithm I"]}},"options":{"fields":["id","difficulty_rating"]},"join":" "},"results":[{"id":2523,"difficulty_rating":"medium-hard"},{"id":2309,"difficulty_rating":"medium-hard"}]}}