Add more unicode related tests to longestCommonSubstring algorithm.

trekhleb · trekhleb · commit af64d12a2363 · 2018-08-28T06:58:43.000+03:00
diff --git a/src/algorithms/string/longest-common-substring/__test__/longestCommonSubstring.test.js b/src/algorithms/string/longest-common-substring/__test__/longestCommonSubstring.test.js
@@ -7,6 +7,16 @@ describe('longestCommonSubstring', () => {
     expect(longestCommonSubstring('', 'ABC')).toBe('');
     expect(longestCommonSubstring('ABABC', 'BABCA')).toBe('BABC');
     expect(longestCommonSubstring('BABCA', 'ABCBA')).toBe('ABC');
+    expect(longestCommonSubstring(
+      'Algorithms and data structures implemented in JavaScript',
+      'Here you may find Algorithms and data structures that are implemented in JavaScript',
+    )).toBe('Algorithms and data structures ');
+  });
+
+  it('should handle unicode correctly', () => {
     expect(longestCommonSubstring('𐌵𐌵**ABC', '𐌵𐌵--ABC')).toBe('ABC');
+    expect(longestCommonSubstring('𐌵𐌵**A', '𐌵𐌵--A')).toBe('𐌵𐌵');
+    expect(longestCommonSubstring('A买B时', '买B时GD')).toBe('买B时');
+    expect(longestCommonSubstring('After test买时 case', 'another_test买时')).toBe('test买时');
   });
 });
diff --git a/src/algorithms/string/longest-common-substring/longestCommonSubstring.js b/src/algorithms/string/longest-common-substring/longestCommonSubstring.js
@@ -1,23 +1,27 @@
 /**
- * @param {string} s1
- * @param {string} s2
+ * @param {string} string1
+ * @param {string} string2
  * @return {string}
  */
-export default function longestCommonSubstring(s1, s2) {
-  // transform s1 & s2 into arrays to allow handling unicodes as single caracter.
-  const [a1, a2] = [s1, s2].map(s => Array.from(s));
+export default function longestCommonSubstring(string1, string2) {
+  // Convert strings to arrays to treat unicode symbols length correctly.
+  // For example:
+  // '𐌵'.length === 2
+  // [...'𐌵'].length === 1
+  const s1 = [...string1];
+  const s2 = [...string2];
 
   // Init the matrix of all substring lengths to use Dynamic Programming approach.
-  const substringMatrix = Array(a2.length + 1).fill(null).map(() => {
-    return Array(a1.length + 1).fill(null);
+  const substringMatrix = Array(s2.length + 1).fill(null).map(() => {
+    return Array(s1.length + 1).fill(null);
   });
 
   // Fill the first row and first column with zeros to provide initial values.
-  for (let columnIndex = 0; columnIndex <= a1.length; columnIndex += 1) {
+  for (let columnIndex = 0; columnIndex <= s1.length; columnIndex += 1) {
     substringMatrix[0][columnIndex] = 0;
   }
 
-  for (let rowIndex = 0; rowIndex <= a2.length; rowIndex += 1) {
+  for (let rowIndex = 0; rowIndex <= s2.length; rowIndex += 1) {
     substringMatrix[rowIndex][0] = 0;
   }
 
@@ -26,9 +30,9 @@ export default function longestCommonSubstring(s1, s2) {
   let longestSubstringColumn = 0;
   let longestSubstringRow = 0;
 
-  for (let rowIndex = 1; rowIndex <= a2.length; rowIndex += 1) {
-    for (let columnIndex = 1; columnIndex <= a1.length; columnIndex += 1) {
-      if (a1[columnIndex - 1] === a2[rowIndex - 1]) {
+  for (let rowIndex = 1; rowIndex <= s2.length; rowIndex += 1) {
+    for (let columnIndex = 1; columnIndex <= s1.length; columnIndex += 1) {
+      if (s1[columnIndex - 1] === s2[rowIndex - 1]) {
         substringMatrix[rowIndex][columnIndex] = substringMatrix[rowIndex - 1][columnIndex - 1] + 1;
       } else {
         substringMatrix[rowIndex][columnIndex] = 0;
@@ -53,7 +57,7 @@ export default function longestCommonSubstring(s1, s2) {
   let longestSubstring = '';
 
   while (substringMatrix[longestSubstringRow][longestSubstringColumn] > 0) {
-    longestSubstring = a1[longestSubstringColumn - 1] + longestSubstring;
+    longestSubstring = s1[longestSubstringColumn - 1] + longestSubstring;
     longestSubstringRow -= 1;
     longestSubstringColumn -= 1;
   }
