Word uyğunluğu ilə Word istifadə ən uzun ümumi prefiks

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur VMware
Geyim SimBaxılıb 23

Sözlərin siyahısını nəzərə alaraq, sözlərin bir-birinə uyğun olaraq bütün sözlərdən ən uzun ümumi prefiksini tapın.

Nümunələr

Input:
siyahı [] = {"alma", "meymun", "aprel"}
Çıxış:
ap
Input:
siyahı [] = {"ulduz", "oğurladı", "buxar", "başla"}
Çıxış:
st

Ən uzun yayılmış prefiks üçün alqoritm

İki sözün ən uzun yayılmış prefiksi,
W1 birinci söz, W2 ikinci söz olsun,

  1. Başlanğıc a sim dəyişən commonPrefix kimi “” (boş simli).
  2. Sözlərdən birinin sonuna çatana qədər eyni zamanda W1 və W2-də keçməyə başlayın.
  3. W1 və W2 simvollarını uyğunlaşdırın, əgər bunlar bərabərdirsə, commonPrefix-ə əlavə edin və hər iki sözdə irəliləyin.
  4. Başqa qayıtma ümumiPrefix

Yuxarıdakı alqoritm N sözlərinin siyahısının ən uzun yayılmış prefiksini tapmaq üçün genişləndirilə bilər,

  1. Siyahıda ilk söz kimi commonPrefix simli dəyişənini başlatın.
  2. Siyahıda indeks 1-dən başlayaraq keçin (o əsaslı indeksləşdirmə).
  3. CommonPrefix-i commonPrefix-in ümumi bir prefiksi və siyahıda mövcud söz kimi yeniləyin.
  4. Keçidin sonunda ortaq qayıt commonPrefix.

Ən uzun yayılmış prefiksin izahı

Bir nümunəyə baxaq,
siyahı [] = {"ulduz", "oğurladı", "buxar", "başla"}

Step 1
commonPrefix = “ulduz”

Step 2
Siyahını indeks 3-dən siyahının sonuna qədər keçərkən 4 və 1-cü addımları təkrarlayın.

Addım 3 və 4
Təkrarlama 1
commonPrefix = ümumi prefiks (commonPrefix, “çaldı”)
commonPrefix = "st"
Təkrarlama 2
commonPrefix = ümumi prefiks (commonPrefix, “buxar”)
commonPrefix = "st"
Təkrarlama 3
commonPrefix = ümumi prefiks (commonPrefix, “start”)
commonPrefix = "st"

Siyahını keçdik və siyahıda olan bütün sözlərin ümumi prefiksi “st” dir. Aydınlaşdırmaq üçün aşağıdakı şəkilə baxın.

Word uyğunluğu ilə Word istifadə ən uzun ümumi prefiksPin

JAVA Kodu

public class LongestCommonPrefixUsingWordByWordMatching {
    // Function to find common prefix of two words
    private static String prefix(String W1, String W2) {
        // Initialize prefix as empty string
        String prefix = "";

        int n1 = W1.length();
        int n2 = W2.length();
        int i = 0, j = 0;

        // Traverse in W1 and W2 simultaneously
        while (i < n1 && j < n2) {
            // If characters of W1 and W2 are equal, append it to answer else return prefix
            if (W1.charAt(i) == W2.charAt(j)) {
                prefix += W1.charAt(i);
                i++;
                j++;
            } else {
                return prefix;
            }
        }

        // All words matched, return prefix
        return prefix;
    }

    private static String longestCommonPrefix(String[] list) {
        // Initialize longest common prefix as first word of list
        String lcp = list[0];
        
        // Traverse the list from index 1 (0 based indexing)
        for (int i = 1; i < list.length; i++) {
            // Update lcp as prefix of lcp and current word
            lcp = prefix(list[i], lcp);
        }
        
        // return lcp
        return lcp;
    }

    public static void main(String[] args) {
        // Example 1
        String list1[] = new String[] {"apple", "ape", "april"};
        System.out.println(longestCommonPrefix(list1));

        // Example 2
        String list2[] = new String[] {"star", "stole", "steam", "start"};
        System.out.println(longestCommonPrefix(list2));
    }
}

Ən uzun yayılmış prefiks üçün C ++ kodu

#include <bits/stdc++.h>
using namespace std;

// Function to find common prefix of two words
string prefix(string W1, string W2) {
    // Initialize prefix as empty string
    string prefix = "";
    
    int n1 = W1.size();
    int n2 = W2.size();
    int i = 0, j = 0;
    
    // Traverse in W1 and W2 simultaneously
    while (i < n1 && j < n2) {
        // If characters of W1 and W2 are equal, append it to answer else return prefix
        if (W1[i] == W2[j]) {
            prefix += W1[i];
            i++;
            j++;
        } else {
            return prefix;
        }
    }

    // All words matched, return prefix
    return prefix;
}

string commonPrefix(vector<std::string> &list) {
    // Initialize longest common prefix as first word of list
    string lps = list.front();
    
    // Traverse the list from index 1 (0 based indexing)
    for (auto itr = list.begin() + 1; itr != list.end(); itr++) {
        // Update lcp as prefix of lcp and current word
        lps = prefix(lps, *itr);
    }
    
    // return lcp
    return lps;
}

int main() {
    // Example 1
    vector<std::string> list1;
    list1.push_back("apple");
    list1.push_back("ape");
    list1.push_back("april");
    cout<<commonPrefix(list1)<<endl;
    
    // Example 2
    vector<std::string> list2;
    list2.push_back("star");
    list2.push_back("stole");
    list2.push_back("steam");
    list2.push_back("start");
    cout<<commonPrefix(list2)<<endl;
    
    return 0;
}
ap
st

Ən Uzun Ümumi Prefiks üçün Mürəkkəblik Analizi

Zaman Mürəkkəbliyi = O (N * siyahıda bir sözün maksimum uzunluğu) 
Kosmik Mürəkkəblik = O (1)
burada N - siyahıda sözlərin ümumi sayı.

References

Translate »