时间戳

首页 > 解决方案 > 给定子字符串和索引，重新组装可能重叠的字符串片段

c++ - 给定子字符串和索引，重新组装可能重叠的字符串片段

问题描述

在不使用任何外部库的情况下，给定子字符串和索引，重新组装可能重叠的字符串片段的优雅方法是什么？

例如，给定 (0, "abc") (1, "bcd") (3, "def") (9, "fff") (11,"f") 实现应该返回 "abcdef"。

该实现还应该能够跟踪尚未组装的字符数。在这种情况下 - 3，而不是 4，因为 (9, "fff") 和 (11,"f") 重叠。

我正在用 c++ 编码并使用多映射和递归，但这似乎很慢。先感谢您！

标签： c++stringalgorithmdata-structures

解决方案

您只需一步即可实现。只需将所有子字符串合并为一个字符串。对未使用的空格使用特殊字符（例如零）。结果是从开始到第一个未使用的空间。非组合字符从第一个未使用的空间开始都是非零。

首先，将所有子字符串合并为一个字符串。它有助于预先计算总长度。在此操作之后，所有未使用的空间都存储零。

struct SubString {
  size_t index;
  std::string substr;
};

auto calculateTotalLength(const std::vector<SubString>& strings) {
  const auto it = std::max_element(
    strings.cbegin(), strings.cend(), [](const auto& a, const auto& b) {
      return (a.index + a.substr.size()) < (b.index + b.substr.size());
  });
  return it != strings.cend() ? it->index + it->substr.size() : 0;
}

auto mergeStrings(const std::vector<SubString>& strings) {
  auto result = std::string(calculateTotalLength(strings), 0);
  for (const auto& s : strings) {
    result.replace(s.index, s.substr.size(), s.substr);
  }
  return result;
}

现在您可以从第一个未使用的空间开始计算所有未组装的字符。

auto countNonAssembled(std::string_view s) {
  const auto start = s.find(static_cast<char>(0));
  return start != std::string_view::npos
             ? std::count_if(std::next(s.cbegin(), start), s.cend(),
                             [](auto ch) { return ch != 0; })
             : 0;
}

结合这两个操作。

 auto assemble(const std::vector<SubString>& strings) {
   const auto result = mergeStrings(strings);
   return std::pair{result.substr(0, result.find(static_cast<char>(0))),
                    countNonAssembled(result)};
 }

 const auto [assembled, nonAssembled] =
   assemble({{0, "abc"}, {1, "bcd"}, {3, "def"}, {9, "fff"}, {11, "f"}});

assert(assembled == "abcdef");
assert(nonAssembled == 3);

时间复杂度与所有子字符串的字符总数成线性关系。

推荐阅读