Java 使用逐字比对的方法查找最长公共前缀

我们给定了一组字符串，我们需要找出它们之间的公共前缀。前缀是一个字符串的子串，它包含零索引，并且长度可以是1到完整字符串的任意长度。我们将实现一个带有解释和时间复杂度和空间复杂度讨论的Java程序。

输入

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

输出

abcd

解释

从所有给定的字符串中，前四个字符相同，剩余字符在所有字符串中都不相同。

输入

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

输出

""

解释

在给定的字符串中，没有一个字符串共享相同的前缀。

比较所有字符串

在这种方法中，我们将逐个遍历所有字符串，并将它们与第一个字符串进行比较，并将答案存储在另一个字符串中。

我们将创建一个用于比较字符串的函数和一个辅助函数，以使代码更整洁。

示例

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循环遍历数组，检查所有字符串的当前字符是否与第一个字符串的字符相同。

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

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

示例

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