字符串比较相同顺序的字符个数

Question

我

Str A = "abcdef"
Str B = "abcdf"

需要一个返回 5（即匹配的字符数）的函数（stA，stB），请注意这些字符需要具有相同的顺序。

例如：

Str A = "abcdef"
Str B = "fedcba",

function(stA, stB) 只会为 'a' 返回 1

伪代码很好...

哦，顺便说一句，考虑到我所有的字符串都将有 <= 40 个字符，O(n ^2) 甚至可能比 O(41n) 算法更好。

Answer 1

我还没有完全测试它，但这似乎对您的测试用例有效（在 JavaScript 中）：

function compare(a, b)
{
    var aChars = a.split('');
    var bChars = b.split('');

    var matches = [];
    var bStart = 0;

    for (var i=0; i < aChars.length; i++)
    {
        for (var j=bStart; j < bChars.length; j++)
        {
            if(aChars[i] == bChars[j])
            {
                matches.push(aChars[i]);
                bStart = j;
                break;
            }
        }
    }

    return matches.length;
}

compare('abcdef', 'abcdf'); // returns 5
compare('abcdef', 'fedcba'); // returns 1

基本上我从字符串 A 的位置 0 和字符串 B 的位置 0 开始。当找到匹配项时，我更改搜索字符串 B 的起始位置，以便它跳过上一节。