Ən Uzun Ümumi Prefiks Leetcode Həlli

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

The Ən Uzun Ümumi Prefiks LeetCode Həlli – “Ən uzun ümumi prefiks” sətirlərin verildiyini bildirir. Bu sətirlər arasında ən uzun ümumi prefiksi tapmalıyıq. Əgər prefiks yoxdursa, boş sətir qaytarın.

Misal:

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

Output: "fl"

Explanation:

• “fl” bütün üç sətir arasında ən uzun ümumi prefiksdir.

Input:  strs = ["dog","racecar","car"]

Output: ""

Explanation:

• Bütün sətirlərin birinci simvolu fərqlidir, ümumi prefiks yoxdur.

Yanaşma

Idea:

1. Bu problemi həll etmək üçün əsas fikir istifadə etməkdir iki döngə.
2. Biz ilk sətri seçib ən uzun ümumi prefiksi tapacağıq.
3. Üçün Ən uzun ümumi prefiks uzunluğu L olması üçün simlər massivi arasında L-1 uzunluğunda ümumi prefiks olmalıdır.
4. Beləliklə, L-dən 0-dan birinci sətirin uzunluğuna qədər başlayın, və hər L üçün biz bütün sətirlərin L-ci simvolunu yoxlayacağıq.
5. Əgər bütün sətirlərin L-ci simvolu eynidirsə, biz prefiksin daha uzunluğunu yoxlamağa davam edəcəyik, əks halda işi bitirmişik.

Kodu

Ən Uzun Ümumi Prefiks C++ Həlli:

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int L = 0;
        for(int i=0;i<strs[0].length();i++){
            int ok = 1;
            for(auto& s:strs){
                if(L>=s.length() or s[L]!=strs[0][L]){
                    ok = 0;
                    break;
                }
            }
            if(ok){
                L++;
            }
            else{
                break;
            }
        }
        return strs[0].substr(0,L);
    }
};

Ən Uzun Ümumi Prefiks Java Həlli:

class Solution {
    public String longestCommonPrefix(String[] strs) {
        int L = 0;
        for(int i=0;i<strs[0].length();i++){
            int ok = 1;
            for(int j=0;j<strs.length;j++){
                if(L>=strs[j].length() || strs[j].charAt(L)!=strs[0].charAt(L)){
                    ok = 0;
                    break;
                }
            }
            if(ok==1){
                L++;
            }
            else{
                break;
            }
        }
        return strs[0].substring(0,L);
    }
}

Ən Uzun Ümumi Prefiks Leetcode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

The zaman mürəkkəbliyi yuxarıdakı koddur O(N*L). Aralıqdakı hər uzunluq üçün [0, L], biz bütün sətirlərin ümumi prefiksə malik olub-olmadığını yoxlayırıq, burada N = sətirlərin ümumi sayı və L sətirin minimum uzunluğudur.

Kosmik Mürəkkəblik

The kosmik mürəkkəblik yuxarıdakı koddur O (1) istifadə etdiyimiz üçün daimi boşluq.