הקידומת הנפוצה הארוכה ביותר באמצעות התאמה בין מילים למילה


רמת קושי בינוני
נשאל לעתים קרובות VMware
מערך מחרוזת

בהינתן רשימת מילים, מצא את הקידומת המשותפת הארוכה ביותר של כל המילים לפי מילים אחר התאמת מילים.

דוגמאות

קלט:
רשימה [] = {“תפוח”, “קוף”, “אפריל”}
פלט:
ap
קלט:
list [] = {“כוכב”, “גנב”, “קיטור”, “התחל”}
פלט:
st

אלגוריתם לקידומת המשותף הארוך ביותר

הקידומת הנפוצה הארוכה ביותר של שתי מילים נמצאת כ,
תן W1 להיות המילה הראשונה ו- W2 להיות המילה השנייה,

  1. אתחל א מחרוזת משתנה commonPrefix כ- "" (מחרוזת ריקה).
  2. התחל לחצות W1 ו- W2 בו זמנית, עד שנגיע לסוף כל אחת מהמילים.
  3. התאם את הדמויות של W1 ו- W2, אם אלה שווים, הוסף אותו ל- CommonPrefix והתקדם בשתי המילים.
  4. Else return commonPrefix

ניתן להרחיב את האלגוריתם שלעיל כדי למצוא את הקידומת הנפוצה הארוכה ביותר של רשימת מילים N כ,

  1. אתחל משתנה מחרוזת commonPrefix כמילה הראשונה ברשימה.
  2. חצה ברשימה החל מאינדקס 1 (אינדקס מבוסס o).
  3. עדכן commonPrefix כקידומת נפוצה של commonPrefix והמילה הנוכחית ברשימה.
  4. בסוף ההחזרה המעבר משותף Prefix.

הסבר לקידומת הנפוצה הארוכה ביותר

שקול דוגמה,
list [] = {“כוכב”, “גנב”, “קיטור”, “התחל”}

שלב 1
commonPrefix = "כוכב"

שלב 2
חזור על שלב 3 ו -4 תוך כדי חציית הרשימה מאינדקס 1 עד סוף הרשימה.

שלב 3 ו -4
איטרציה 1
commonPrefix = קידומת משותפת של (commonPrefix, "גנב")
commonPrefix = “st”
איטרציה 2
commonPrefix = קידומת משותפת של (commonPrefix, "steam")
commonPrefix = “st”
איטרציה 3
commonPrefix = קידומת משותפת של (commonPrefix, "התחל")
commonPrefix = “st”

עברנו את הרשימה והקידומת המשותפת של כל המילים ברשימה היא "st". ראה את התמונה למטה להבהרה.

הקידומת הנפוצה הארוכה ביותר באמצעות התאמה בין מילים למילה

קוד JAVA

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

קוד C ++ לקידומת המשותף הארוך ביותר

#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

ניתוח מורכבות לקידומת הנפוצה הארוכה ביותר

מורכבות זמן = O (N * אורך מרבי של מילה ברשימה) 
מורכבות שטח = O (1)
כאשר N הוא המספר הכולל של המילים ברשימה.

הפניות