C# 或 JavaScript：确定字符串中的公共前缀

发布于 2024-12-08 12:08:05 字数 427 浏览 0 评论 0原文

可能的重复：
查找字符串的公共前缀

假设我有一个字符串数组。该数组至少有两个元素，也可能有更多。数组中的每个字符串至少有两个字符，也可能更多，并且至少每个字符串的第一个字符是相同的。

给定所述字符串数组，确定所有字符串共享的最长前缀的最有效方法是什么？

例如，给定 ['cowgirl', 'cowboy']，公共前缀为 cow。或者，给定 ['a', 'abs', apples']，公共前缀是 a。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

一城柳絮吹成雪 2024-12-15 12:08:05

我认为最简单的算法，也许也是最有效的算法，就是按顺序检查单词，将迄今为止最长的公共前缀与每个单词进行比较，以确定可以保留多少单词。使用第一个字符串作为初始前缀。

编辑：下面是一些执行此操作的 Javascript 代码：

function findLongestPrefix(list) {
    var prefix = list[0];
    var prefixLen = prefix.length;
    for (var i = 1; i < list.length && prefixLen > 0; i++) {
        var word = list[i];
        // The next line assumes 1st char of word and prefix always match.
        // Initialize matchLen to -1 to test entire word.
        var matchLen = 0;
        var maxMatchLen = Math.min(word.length, prefixLen);
        while (++matchLen < maxMatchLen) {
            if (word.charAt(matchLen) != prefix.charAt(matchLen)) {
                break;
            }
        }
        prefixLen = matchLen;
    }
    return prefix.substring(0, prefixLen);
}

I think the simplest algorithm, and perhaps the most efficient, is to just examine the words in sequence, comparing the longest common prefix so far to each word to determine how much of it you can keep. Use the first string as the initial prefix.

EDIT: Here's some Javascript code that does the work:

function findLongestPrefix(list) {
    var prefix = list[0];
    var prefixLen = prefix.length;
    for (var i = 1; i < list.length && prefixLen > 0; i++) {
        var word = list[i];
        // The next line assumes 1st char of word and prefix always match.
        // Initialize matchLen to -1 to test entire word.
        var matchLen = 0;
        var maxMatchLen = Math.min(word.length, prefixLen);
        while (++matchLen < maxMatchLen) {
            if (word.charAt(matchLen) != prefix.charAt(matchLen)) {
                break;
            }
        }
        prefixLen = matchLen;
    }
    return prefix.substring(0, prefixLen);
}

回复收藏 0 原文