使用逐词匹配查找最长公共前缀的 JavaScript 程序

---

前缀是从给定字符串的第零个索引开始的子字符串，其大小可以是从 1 到字符串的完整长度的任何值。我们得到一组字符串，我们必须在 JavaScript 编程语言中找到它们之间的公共前缀。我们必须实现逐词匹配方法，在该方法中我们将匹配单词而不是完整的字符串。

输入

arr = ["zefkefgh", "zefkdefij", "zeffdzy", "zefkdabacd"];

输出

zef

解释

在所有给定的字符串中，我们的前三个字符相同，其余字符对它们来说并不相同

输入

arr = ["zefkefgh", "bcdefij", "acdzy", "abzefkacd"]

输出

""

解释

在给定的字符串中，没有一个共享相同的前缀，因此我们返回了空字符串。

比较所有字符串

比较所有字符串意味着我们将第一个字符串作为初始字符串，然后将所有其余字符串与当前字符串进行比较，并将最小的前缀作为答案。

示例

// creating a function to find the longest common prefix of two given strings     
function commonPre(str1, str2){
   var ans = "";
   var len1 = str1.length; // length of the string 1
   var len2 = str2.length; // length of the string 2
   // comparing both teh strings until they are same 
   var i = 0; // pointer to traverse over both the string     
   while(i < len1 && i < len2){
      if(str1[i] != str2[i]){
      // break the string if the current character is not same 
         break;
      } else{
          // add the current character to the answer string 
          ans += str1[i];
      }
      i++;
   }
   return ans; // return the answer 
} 
// helper function that will return the final answer 
function helper(arr, len){
   var pre = arr[0]; // initializing the prefix variable     
   // comparing the zeoth string with all the string 
   for (var i = 1; i < len; i++){
      pre = commonPre(pre, arr[i]);
   }
   return pre; // return the final answer 
}        
// given array 
var arr = ["zefkefgh", "zefkdefij", "zeffdzy", "zefkdabacd"];
var len = arr.length; // getting length of the given array
var ans = helper(arr, len); // calling to the function 
if (ans.length > 0){
   // answer string is not empty 
   console.log("The longest common prefix among the given strings is: " + ans);
} else{
   // answer string is empty 
   console.log("There is no common prefix among the given strings");
}

输出

The longest common prefix among the given strings is: zef

时间和空间复杂度

上述代码的时间复杂度为 O(N*M)，其中 N 是字符串的数量，M 是字符串的长度。

上述代码的空间复杂度为 O(M)，因为我们使用了字符串来存储公共前缀。

逐词匹配

在这种方法中，我们将遍历第一个字符串，并使用 for 循环遍历数组，并检查所有字符串的当前字符是否与第一个字符串的当前字符相同。

如果任何字符串的大小等于当前指针或值不同，那么我们将停止进一步搜索，否则我们将当前字符添加到答案中并进一步移动。

最后，我们将返回字符串并在主函数中打印答案。

示例

// helper function that will return the final answer 
function helper(arr, len){
   var ans = ""; // string to store the answer         
   //traversging over the first string 
   for (var i = 0; i < arr[0].length; i++) {
      var flag = true; // boolean variable to keep track         
      // compare all the string with the first string current word
      for(var j = 1; j < len; j++){
         if(arr[j].length == i){
            // current string is smallest so, break the loop 
            flag = false; 
            break;
         }
         else if(arr[j][i] != arr[0][i]){
            // current string's current character is not same 
            flag = false; 
            break;
         } else{
             // the current character is same for both the strings 
             continue;
          }
       }       
       if (flag) {
          ans += arr[0][i];
       } else {
          break;
      }
   }
   return ans; // returning the answer
}        
// given array 
var arr = ["zefkefgh", "zefkdefij", "zeffdzy", "zefkdabacd"];
var len = arr.length; // getting length of the given array
var ans = helper(arr, len); // calling to the function 
if (ans.length > 0){
   // answer string is not empty 
   console.log("The longest common prefix among the given strings is: " + ans);
} else{
   // answer string is empty 
   console.log("There is no common prefix among the given strings");
}

输出

The longest common prefix among the given strings is: zef

时间和空间复杂度

上述代码的时间复杂度为 O(N*M)，其中 N 是字符串的数量，M 是字符串的长度。

上述代码的空间复杂度为 O(M)，因为我们使用了字符串来存储公共前缀。

结论

在上面的代码中，我们实现了一个 JavaScript 程序来查找给定字符串的公共前缀。我们实现了两种方法，一种是通过比较所有字符串的直接遍历方法，另一种是逐词匹配方法。两种字符串的时间复杂度均为 O(N*M)。