使用逐詞匹配查詢最長公共字首的 Java 程式

---

在本文中，我們將探討如何使用 Java 中的兩種不同方法來查詢給定字串集中的最長公共字首。我們將首先討論一種直接比較所有字串以查詢最長字首的方法，然後轉向逐詞匹配的方法。

問題陳述

給定一組字串，我們必須找到它們之間所有字串的公共字首。字首是字串的一個子串，包含索引為零的字元，其長度可以從 1 到整個字串。

輸入 1

string arr[] = {"abcdefgh", "abcdefij", "abcdzy", "abcdabacd"};

輸出 1

abcd

解釋

在所有給定的字串中，前四個字元相同，其餘字元並非全部相同。

輸入 2

string arr[] = {{"abcdefgh", "bcdefij", "acdzy", "abcdabacd"};}

輸出 2

""

解釋

在給定的字串中，沒有一個共享相同的字首。

不同的方法

以下是使用逐詞匹配查詢最長公共字首的不同方法。

• 比較所有字串
• 逐詞匹配

比較所有字串

在這種方法中，我們將逐一遍歷所有字串，將它們與第一個字串進行比較，並將結果儲存在另一個字串中。

以下是使用逐詞匹配查詢最長公共字首的步驟：

• 初始化字首變數，並將第一個字串 arr[0] 作為初始字首。
  
• 使用 for 迴圈 遍歷陣列，並將當前字串與字首進行比較。
  
• 使用 while 迴圈 比較字串，並在輔助方法 commonPre 中使用 while 迴圈比較兩個字串中相同位置的字元，直到找到不匹配或迴圈結束。
• 使用 if 條件 檢查字元是否不匹配，如果字元不匹配則中斷迴圈，如果匹配則將字元附加到字首。
  
• 與每個字串比較後更新字首，並使用公共部分更新字首。
• 迴圈完成後，返回最終的最長公共字首。

示例

public class Solution{
   // creating a function to find the longest common prefix of two given strings     
   static String commonPre(String str1, String str2){
      String ans = "";
      int len1 = str1.length(); // length of the string 1
      int len2 = str2.length(); // length of the string 2
      // comparing both teh strings until they are same 
      int i = 0; // pointer to traverse over both the string       
      while(i < len1 && i < len2){
         if(str1.charAt(i) != str2.charAt(i)){
            break;
         } else{
            // add the current character to the answer string 
            ans += str1.charAt(i);
         }
         i++;
      }
      return ans; // return the answer 
   } 
   // helper function that will return the final answer 
   static String helper(String arr[], int len){
      String pre = arr[0]; // initializing the prefix variable         
      // comparing the zeoth string with all the string 
      for (int i = 1; i < len; i++){
         pre = commonPre(pre, arr[i]);
      }
      return pre; // return the final answer 
   } 
   public static void main(String[] args) {        
      // given array 
      String arr[] = {"abcdefgh", "abcdefij", "abcdzy", "abcdabacd"};
      int len = arr.length; // getting length of the given array 
      String ans = helper(arr, len); // calling to the function  
      if (ans.length() > 0){
          // answer string is not empty 
          System.out.printf("The longest common prefix among the given strings is: %s", ans);
      } else{
         // answer string is empty 
         System.out.printf("There is no common prefix among the given strings");
      }
   }
}

輸出

The longest common prefix among the given strings is: abcd

時間和空間複雜度

上述程式碼的 時間複雜度 為 O(N*M)，其中 N 是字串的數量，M 是字串的長度。

上述程式碼的 空間複雜度 為 O(M)，因為我們使用了字串來儲存公共字首。

逐詞匹配

在這種方法中，我們將遍歷第一個字串，並使用 for 迴圈遍歷陣列，檢查所有字串的當前字元是否與第一個字串的當前字元相同。

• 建立一個輔助函式 helper 來查詢最長公共字首。
  
• 首先使用 for 迴圈 遍歷第一個字串的字元。
  
• 對於每個字元，檢查所有其他字串在當前索引處是否具有相同的字元。
  
• 如果任何字串較短或具有不同的字元，則中斷迴圈。
  
• 將匹配的字元新增到結果字串中，並繼續檢查，直到找到不匹配。
  
• 在主方法中，將字串陣列傳遞給輔助函式，如果最長公共字首不為空，則列印它。

示例

public class Solution{
   // helper function that will return the final answer 
   static String helper(String arr[], int len){
      String ans = ""; // string to store the answer         
      //traversging over the first string 
      for (int i = 0; i < arr[0].length(); i++) {
         boolean flag = true; // boolean variable to keep track             
         // compare all the string with the first string current word
         for(int 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].charAt(i) != arr[0].charAt(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].charAt(i);
         } else {
            break;
         }
      }
      return ans; // return the answer
   } 
   public static void main(String[] args) {      
      // given array 
      String arr[] = {"abcdefgh", "abcdefij", "abcdzy", "abcdabacd"};
      int len = arr.length; // getting length of the given array 
      String ans = helper(arr, len); // calling to the function  
      if (ans.length() > 0){
         // answer string is not empty 
         System.out.printf("The longest common prefix among the given strings is: %s", ans);
      } else{
            // answer string is empty 
            System.out.printf("There is no common prefix among the given strings");
      }
   }
}

輸出

The longest common prefix among the given strings is: abcd

時間和空間複雜度

上述程式碼的時間複雜度為 O(N*M)，其中 N 是字串的數量，M 是字串的長度。

上述程式碼的空間複雜度為 O(M)，因為我們使用了字串來儲存公共字首。

結論

在上述程式碼中，我們實現了一個 Java 程式來查詢給定字串的公共字首。我們實現了兩種方法，一種是透過比較所有字串的直接遍歷方法，另一種是逐詞匹配方法。兩種字串的時間複雜度均為 O(N*M)。