使用逐字匹配的最长公共前缀


难度级别 中等
经常问 VMware的
排列

给定单词列表,逐单词匹配地找到所有单词中最长的公共前缀。

例子

输入:
list [] = {“苹果”,“猿”,“四月”}
输出:
ap
输入:
list [] = {“星”,“偷”,“蒸汽”,“开始”}
输出:
st

最长公共前缀的算法

发现两个单词的最长公共前缀为:
令W1为第一个单词,W2为第二个单词,

  1. 初始化一个 绳子 变量commonPrefix为“”(空字符串)。
  2. 同时开始在W1和W2中遍历,直到到达任何一个单词的末尾。
  3. 匹配W1和W2的字符,如果相等,则将其追加到commonPrefix并在两个词中前进。
  4. 其他返回commonPrefix

可以扩展上述算法以找到N个单词的列表中最长的公共前缀,例如,

  1. 将字符串变量commonPrefix初始化为列表中的第一个单词。
  2. 从索引1(基于o的索引)开始遍历列表。
  3. 将commonPrefix更新为commonPrefix和列表中当前单词的公共前缀。
  4. 遍历结束时,返回commonPrefix。

最长公共前缀的说明

考虑一个例子,
list [] = {“星”,“偷”,“蒸汽”,“开始”}

步骤
commonPrefix =“星级”

步骤
从索引3遍历列表到列表末尾时,重复步骤4和1。

步骤3和4
迭代1
commonPrefix =的公共前缀(commonPrefix,“ stole”)
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是列表中的单词总数。

參考資料