Задача: ищем самый длинный общий префикс у элементов массива строк

Чтобы решить эту задачу, мы будем использовать принцип «скользящего окна». Его суть в том, что мы берём две строки и начинаем посимвольно сравнивать их, как бы смотря на них через окно.

Для нашей задачи это самый простой и очевидный метод решения. Мы возьмём два указателя — начала и конца — и будем перемещать их в зависимости от условий: нашли или не нашли одинаковую последовательность символов.

На старте алгоритма первая строка массива будет считаться общим префиксом. В процессе мы будем сравнивать её с другими строками и отрезать с конца символы, которые не совпадают. И так с каждой строкой массива.

Полный алгоритм такой:

• Сначала проверяем размер массива: если массив пустой, то и общий префикс — пустая строка. А если в массиве только один элемент, то он и будет общим префиксом.
• В остальных случаях берём первую строку массива и принимаем её за самый длинный общий префикс.
• Ставим два указателя: один будет следить за индексом последнего символа, который совпал с нашим общим префиксом, а второй будет перемещаться по строкам посимвольно.
• Перебираем элементы массива, начиная со второго — сравниваем символы в этом элементе с символами общего префикса. Если символы равны, увеличиваем индекс общего префикса на один, если нет — просто идём дальше.
• После проверки очередной строки массива отрезаем от общего префикса лишние символы — по индексу, который сохранён в нашем указателе.

Вот как этот алгоритм будет реализован на Java:

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;
  }