Блог

Вопрос:

Напишите функцию для поиска самой длинной строки общего префикса среди массива строк. Если общего префикса нет, верните пустую строку «».

Пример 1:

Ввод: [«цветок», «поток», «полет»]
Вывод: «fl»

Пример 2:

Ввод: [«собака», «гоночный автомобиль», «автомобиль»]
Вывод: «»

Объяснение: Среди входных строк нет общего префикса.

Код:

 public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs==null || strs.length==0)
            return "";
        for(int i=0;i<strs[0].length();i  ) {
            char x = strs[0].charAt(i);
            for(int j=0;j<strs.length;j  ) {
                if((strs[j].length()==i)||(strs[j].charAt(i)!=x)) {
                    return strs[0].substring(0,i);
                }
            }
        }
        return strs[0];
    }
}
  

Это второе решение, но я не понимаю внутреннего цикла.
Я думаю, что если второй элемент в strs возвращает строку и завершает цикл for, у третьего элемента не будет возможности для сравнения.

Вы должны проверить одинаковую позицию во всех словах и просто сравнить ее.

          positions
word    0 1 2 3 4 5
=====================
w[0]    F L O W E R
w[1]    F L O W
w[2]    F L I G H T
  

В Java:

 class Main {

    public static void main(String[] args) {
        String[] words = {"dog","racecar","car"};

        String prefix = commonPrefix(words);

        System.out.println(prefix);
        // return empty string

        String[] words2 = {"dog","racecar","car"};

        String prefix2 = commonPrefix(words2);

        System.out.println(prefix2);
        // Return "fl" (2 letters)
    }

    private static String commonPrefix(String[] words) {
        // Common letter counter
        int counter = 0;

        external:
        for (int i = 0; i < words[0].length(); i  ) {

            // Get letter from first word
            char letter = words[0].charAt(i);

            // Check rest of the words on that same positions
            for (int j = 1; j < words.length; j  ) {
                // Break when word is shorter or letter is different
                if (words[j].length() <= i || letter != words[j].charAt(i)) {
                    break external;
                }
            }

            // Increase counter, because all of words
            // has the same letter (e.g. "E") on the same position (e.g. position "5")
            counter  ;
        }

        // Return proper substring
        return words[0].substring(0, counter);
    }

}
  

Ваш первый цикл повторяется по всем символам в первой строке массива. Второй цикл проверяет char в i расположении всех строк массива. Если символы не совпадают или длина строки совпадает с i , возвращается результат подстроки.

Я думаю, что лучший способ понять это — отладить этот пример.

Если символ char во второй строке отличается от символа char в первой, то правильно возвращать, поскольку это означает, что общий префикс заканчивается на этом. Проверять третью и следующие строки не обязательно.

В основном он возвращается, как только находит символ несоответствия.

Если бы мы сначала отсортировали их, то это было бы очень просто, нам нужно было бы только пойти и сравнить первый и последний элемент в присутствующем там векторе, так что код был бы таким, это код C для реализации.

 class Solution {
public:
    string longestCommonPrefix(vector<string>amp; str) {
        int n = str.size();
        if(n==0) return "";

        string ans  = "";
        sort(begin(str), end(str));
        string a = str[0];
        string b = str[n-1];

        for(int i=0; i<a.size(); i  ){
            if(a[i]==b[i]){
                ans = ans   a[i];
            }
            else{
                break;
            }
        }

        return ans;

    }
};
  

 public class Solution {
public string LongestCommonPrefix(string[] strs) {


    if(strs.Length == 0)
    {
        return string.Empty;

    }

    var prefix = strs[0];
    for(int i=1; i<strs.Length; i  ) //always start from 1.index
    {
        while(!strs[i].StartsWith(prefix)) 
        {
            prefix = prefix.Substring(0, prefix.Length-1);

        }

    }
    return prefix;

    
}
}