我有两个字符串，它们的长度都相同。而且我必须检查它们是否可以表示为 XYZ 和 XZY，其中 Y 和 Z 不为空。

我的解决方案是“吃掉”两个字符串的相同首字母，然后找到最长公共(public)子串以供休息。然后检查第一个字符串的其余部分和第二个字符串的其余部分(没有 LCS)是否相等。问题是，我听说过 O(N) 的内存复杂度算法，但我发现的只是 O(MN)。我的内存力有限，所以这对我很重要。

第二种解决方案是使用 "(.*)(.+)(.+)\1\3\2"正则表达式，但这是非常糟糕的解决方案。

有人有其他想法吗？

最佳答案

也许是这样的:

bool test(string& s1, string& s2)
{
    if (s1.size() != s2.size())
    {
        return false;
    }
    for (size_t i = 1; i < s1.size()-2; i++)
    {
        if (s1.substr(0,i) != s2.substr(0,i)) return false;

        for (size_t j = 1; j < s1.size()-i; j++)
        {
            string x1 =s1.substr(i,j);
            string x2 =s1.substr(i+j);
            string y1 = s2.substr(i, s1.size()-i - j);
            string y2 = s2.substr(s1.size()-j);
            if ((x1==y2) && (x2==y1))
            {
                cout << "X: " << s1.substr(0,i) << endl;
                cout << "Y Z: " << x1 << " " << x2 << endl;
                cout << "Z Y: "<< y1 << " " << y2 << endl << endl;
                return true;
            }
        }

    }
    return false;
}

int main()
{
    string s1 {"abcbd"};
    string s2 {"abdbc"};

    if (test(s1, s2))
    {
        cout << "OK" << endl;
    }
    else
    {
        cout << "NOT OK" << endl;
    }
    return 0;
}

如果内存对您来说是个大问题，您可以通过逐个字符比较来避免子字符串。例如:

        if (s1.substr(0,i) != s2.substr(0,i)) return false;

可以替换为

        for (size_t z = 0; z < i; z++)
        {
            if (s1[z] != s2[z]) return false;
        }

同样，您可以通过引入两个类似的 for 循环来避免字符串 x1、x2、y1 和 y2，您可以在其中逐个字符地进行比较。

代码会更难阅读和理解，但会占用更少的内存。

bool test(string& s1, string& s2)
{
    size_t N = s1.size();
    if (N != s2.size())
    {
        // s1 and s2 must have same length
        return false;
    }

    // i is length of X
    for (size_t i = 1; i < s1.size()-2; i++)
    {
        // Check that X of length i exists in both s1 and s2
        for (size_t k = 0; k < i; k++)
        {
             if (s1[k] != s2[k]) return false;
        }

        // Now check for YZ in s1[i..N-1] and ZY in s2[i..N-1]
        //
        // j is length of Y
        // N-i-j is length of Z
        for (size_t j = 1; j < N-i; j++)
        {
            // Is s1[i..i+j-1] == s2[N-j..N-1]?
            bool b1 = true;
            for (size_t k = 0; k < j; k++)
            {
                if (s1[i+k] != s2[N-j+k]) b1=false;
            }

            // Is s1[i+j..N-1] == s2[i..N-j-1]?
            bool b2 = true;
            for (size_t k = 0; k < (N-i-j); k++)
            {
                if (s1[i+j+k] != s2[i+k]) b2=false;
            }

            if (b1 && b2)
            {
                // Success!

                // For debug the value of i and j
                // can be used to output the substrings
                // using for-loops
                cout << "X=";
                for (size_t k = 0; k < i; k++)
                {
                    cout << s1[k];
                }
                cout << endl;

                cout << "Y=";
                for (size_t k = i; k < (i+j); k++)
                {
                    cout << s1[k];
                }
                cout << endl;

                cout << "Z=";
                for (size_t k = (i+j); k < N; k++)
                {
                    cout << s1[k];
                }
                cout << endl;


                return true;
            }
        }
    }
    return false;
}

int main()
{
    string s1 {"abcbd"};
    string s2 {"abdbc"};

    if (test(s1, s2))
    {
        cout << "OK" << endl;
    }
    else
    {
        cout << "NOT OK" << endl;
    }
    return 0;
}

关于c++ - 两个字符串 XYZ 和 XZY，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30987602/