通过重复增加字符串前缀的字母顺序来确定字符串是否可转换为另一个字符串

Question

下面是爱丽丝与弦乐，黑客地球上的一个编程挑战：

两个由小写英文字母组成的字符串A和B是兼容的，如果它们相等或可以通过以下步骤使它们相等-- any次数：

• 从字符串A (可能为空)中选择一个前缀，并将前缀中所有字符的字母值增加相同的有效数量。例如，如果字符串是xyz，并且我们选择前缀xy，那么我们可以通过增加字母值1将其转换为yz，但是如果选择前缀xyz，则不能增加字母值。

您的任务是确定给定的字符串A和B是否兼容。输入格式第一行: String A下一行: String B输出格式为每个测试用例，打印YES如果字符串A可以转换为string B，否则打印NO。约束\DeclareMathOperator{\len}{len} 1 \leq \len(A) \leq 1\,000\,000 \\ 1 \leq \len(B) \leq 1\,000\,000 \\

你能回顾一下我的解决方案吗？请评论任何改善的方面，如可读性，注释用法，进一步提高速度/内存使用，等等。

/*
HackerEarth
https://www.hackerearth.com/practice/algorithms/string-algorithm/basics-of-string-manipulation/practice-problems/algorithm/aliceandstrings-9da62aa7/
*/

#include 

/*
Recusrsively checks if string A can be converted to B by incrementing the prefixes:

eg:
A = abaca B = cdbda
[step 1]bcbda (prefix abac incremented by 1)
[step 2]bc[b]da cd[b]da (don't take bcb as a prefix because b is already matched)
[step 3]cdbda -----> so convertible (incrementing prefix bc)
*/
bool transformable(std::string& A, std::string& B, int last_index)
{
    if (A.compare(0, last_index, B, 0, last_index) == 0)
    {
        return true;
    }
    else
    {
        if (A[last_index] == B[last_index])
        {
            return transformable(A, B, --last_index);
        }
        else
        {
            if (A[last_index] > B[last_index])
            {
                return false;
            }
            else
            {
                while(A[last_index] != B[last_index])
                {
                    for(int i = 0; i <= last_index; i++)
                    {
                        A[i] += ('b' - 'a');
                    }
                }

                return transformable(A, B, --last_index);
            }

        }

    }

}

int main()
{
    std::string A;
    std::string B;

    std::cin >> A >> B;

    if (A.length() != B.length())
    {
        std::cout << "NO" << std::endl;
        return 0;
    }

    if (transformable(A, B, A.length() - 1))
        std::cout << "YES" << std::endl;
    else
        std::cout << "NO" << std::endl;

    return 0;
}

Answer 1

代码评审

一般来说，代码看起来很好，并且遵循一致的样式。一些小的观察：

• 失踪的#include 。
• 当std::endl足够时，不要使用\n。std::endl刷新缓冲区，而\n不刷新缓冲区。不必要的冲洗会导致性能下降。见std::endlvs\n。使用std::cout << "YES\n"；而不是std::cout << "YES“<< std::endl；除非冲洗是网站的要求(我希望不会)。
• 因为我们依赖于小写字母的连续编码，所以'B' - 'A'只是1。A[i] += 1变成++A[i]。

更好的算法

也就是说，代码的逻辑过于复杂。嵌套控制语句的许多级别使代码难以遵循。这样做有一个更简单的算法:确定A是否可以转换为B，

• 取对应位置之间的差异B[i] - A[i]；
• 从这些差异中形成一个序列；
• 将序列加0(以防止bbbbb => aaaaa)；
• 测试此序列是否按非升序排序。

例如：

• 对于A = "abcde"，B = "ccdde"，差异的顺序是21100，所以转换是可能的(abcde => bcdde => ccdde)；
• 对于A = "abcde"，B = "bbcce"，差异的顺序是10010，所以转换是不可能的(尝试一下)。

下面(大致)是我如何把所有的东西组合在一起的：

#include 
#include 
#include 
#include 
#include 
#include 

bool transformable(std::string_view a, std::string_view b)
{
    if (a.size() != b.size()) {
        return false;
    }
    std::vector diff_sequence(a.size() + 1);
    std::transform(b.begin(), b.end(), a.begin(), diff_sequence.begin(), std::minus<>{});
    diff_sequence.back() = 0;
    return std::is_sorted(diff_sequence.begin(), diff_sequence.end(), std::greater<>{});
}

int main()
{
    std::string A;
    std::string B;

    std::cin >> A >> B;

    if (transformable(A, B)) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

(现场演示)

(将std::string_view替换为const std::string&，如果C++17不可用，则删除C++17，对于具有竞争力的编程站点，C++17就是这种情况。)

transformable函数可以使用范围-v3库进行简化：

namespace views = ranges::views;

bool transformable(std::string_view a, std::string_view b)
{
    return ranges::is_sorted(
        views::concat(
            views::transform(b, a, std::minus<>{}),
            views::single(0)
        ), std::greater<>{});
}

(现场演示)