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)。