使用逐詞匹配查詢最長公共字首的 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)。