使用逐词匹配查找最长公共前缀的 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)。