Longest Common Prefix

https://leetcode.com/problems/longest-common-prefix/

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Solution:

In this task, again, we can find an important pattern for the future. That is the easiest version of a sliding window. In this pattern, we have start and end pointers and move them depending on the condition.

In our case, the first word will have the longest common prefix. Then we have to compare the first word with the next and cut it to the longest common prefix. And we have to do it for all elements in the array.

Time complexity O(n) --> we should iterate over the array.

Space complexity O(1) --> we need a constant space. Like the largest needed length will be the first word.

  public String longestCommonPrefix(String[] strs) {
    if(strs.length == 0){
      return "";
    }
    if (strs.length == 1){
      return strs[0];
    }
     
    String rez = strs[0];
    for(int i = 1; i < strs.length; i ++){
      String cur = strs[i];
      int reader = 0;
      int lastCommon = 0;
      while(reader < rez.length() && reader < cur.length()){
        if(rez.charAt(reader) == cur.charAt(reader)){
          lastCommon ++;
        } else {
          break;
        }
        reader++;
      }
      rez = rez.substring(0, lastCommon);
    }
    return rez;
  }