时间戳

首页 > 解决方案 > 给定一个等长字符串数组

c++ - 给定一个等长字符串数组

问题描述

给定一个相等长度的字符串数组，检查是否可以重新排列字符串，使得在重新排列后连续位置的字符串会相差一个字符。

例子

对于 inputArray = ["aba", "bbb", "bab"]，输出应为 stringsRearrangement(inputArray) = false。

所有重排都不满足描述条件。

对于 inputArray = ["ab", "bb", "aa"]，输出应该是 stringsRearrangement(inputArray) = true。

字符串可以按以下方式重新排列：“aa”、“ab”、“bb”。

编码：

    bool stringsRearrangement(std::vector<std::string> v) {
    sort(v.begin(), v.end());
    int i,j,count=0;
    do {
        for(i=0;i<v.size()-1;i++) {
            count=0; 
            for(j=0;j<v[0].size();j++) 
                if(v[i][j]!=v[i+1][j]) {
                    count++;
                    if(count==2)
                        break;
                }
            if(count!=1) 
                break;

        }
        if(i==v.size()-2 && j==v[0].size()-1 && count==1)
            return true;

    } while(next_permutation(v.begin(),v.end()));

    return false;
}

例如，代码不起作用，inputArray: ["ab", "bb", "aa"]或者inputArray: ["a", "b", "c"]经过 4 小时思考后找不到错误。

标签： c++

解决方案

按子问题拆分函数以简化代码：

std::size_t hamming_distance(const std::string& s1, const std::string& s2)
{
    std::size_t res = 0;
    for (std::size_t i = 0; i != s1.size(); ++i) {
        res += s1[i] != s2[i];
    }
    return res;
#if 0 // or in C++17
    return std::transform_reduce(
        s1.begin(), s1.end(),
        s2.begin(),
        0u,
        std::not_equal_to<>{},
        std::plus<>{});
#endif
}

bool isAnRearrangement(const std::vector<std::string>& v)
{
    return std::adjacent_find(v.begin(), v.end(),
                              [](const std::string& s1, const std::string& s2){
                                  return hamming_distance(s1, s2) != 1;   
                              }) == v.end();
}

bool stringsRearrangement(std::vector<std::string> v) {
    std::sort(v.begin(), v.end());
    do {
        if (isAnRearrangement(v)) {
            return true;
        }
    } while (std::next_permutation(v.begin(),v.end()));
    return false;
}

演示

然后您可以轻松地测试每个部分：

  • 你计算正确hamming_distance("aba", "bbb")吗？
  • 哪个是结果 isAnRearrangement({"aa", "ab", "bb"})？
  • 等等...

对于您的代码，您会在出现错误的情况下中断循环，因此您的条件是检查循环是否在最后没有中断的情况下结束，但i/的值j将分别为v.size()-1和v[0].size()。因此，使用 sub 函数，您只需使用return false;而不是break;和return true;代替您的条件return true;。

演示

推荐阅读