如何使用STL算法找到字符串中分隔两个不同字母的最短星号序列？

Question

我有一个像这样的字符串：

A*A**B***A**

我对两个不同字母之间的星号序列感兴趣，特别是我需要找到最短序列的长度。 对于上面的字符串，答案当然是2：A**B

我可以使用传统的循环轻松解决此问题，就像我习惯的那样：

const string s = "A*A**B***A**";
string::size_type last_letter=-1, min_seq_len=s.size();
for(int i = 0; i < s.size(); i++) {
    if(last_letter == -1 || s[i] == '*' || s[i] == s[last_letter]) {
        if(s[i] != '*') {
            last_letter = i;
        }
    } else {
        min_seq_len = min(min_seq_len, i-last_letter-1);
        last_letter = i;
    }
}

不过，是否有任何方法可以使用C++算法库、迭代器等来实现这一点呢？

我之所以问这个问题，是因为我注意到我在学习如何使用这些工具来解决算法问题时遇到了困难，相反，我发现手写循环更容易。我想最终学会操作C++算法、范围、迭代器等。

- user4385532

Answer 1

你也可以使用 string 的 find_first_not_of 方法来实现这个功能。

size_t min(str.length()), prev(0), found(0);
while((found = str.find_first_not_of("*", prev)) != std::string::npos) {
  if (str[found] != str[prev] && found - prev < min) {
    min = found + 1 - prev;
  }
  prev = found + 1;
}

演示

- pergy

Answer 2

我对两个不同字母之间的星号序列感兴趣，特别是需要找到最短序列的长度。

你需要最小化某些东西。你可以使用std::min_element来实现。

那个东西是一堆“字母+星号+字母”块。你可以使用std::find_if来查找非星号字符。

然后，你需要在算法之间编写一些粘合剂，可以将其隐藏在类似STL的接口后面。例如：

auto letter_pairs = letter_pair_generator(s);
const auto min_seq_len = std::min_element(
    std::begin(letter_pairs), std::end(letter_pairs),
    [](const auto& x) { return x.asterisk_count(); });

其中letter_pair_generator是一个适配器，它在std::string上公开了类似容器的接口，该接口返回带有星号的不同字母对。例如：

string s = "A*A**B***A**";
for(const auto& p : letter_pair_generator(s)) cout << p;

A*A**B A**B A**B***A B***A

---

有时手写循环比多次调用更清晰、更快。这并不是本质上的问题。使用循环，并将其包装成更安全/更好的接口。但我发现手写循环更容易。

- Vittorio Romeo

---

注意，一堆"字母+星号+字母"的块: 要小心，因为一个字母可能是两个不同的“块”的一部分。 - Solomon Slow

Answer 3

我需要说的是，使用标准库并没有带来很大的改进。但例如，如果没有不同字母的要求，std::regex示例将会简单得多。无论如何，这是我的尝试。

std::string::find_first_not_of 的用法

int best = s.size();
int prev = -1;
int next;

while ((next = s.find_first_not_of("*", prev+1)) >= 0) {
    if (prev >= 0 && s[prev] != s[next]) {
        best = min(best, next - prev - 1);              
    }
    prev = next;
}  

可运行的：https://ideone.com/xdhiQt

std::regex用法:

regex r("(?=([^*][*]*[^*]))");

int best = s.size();
for (auto i = sregex_iterator(s.begin(), s.end(), r); i != sregex_iterator(); ++i) {
    int pos = i->position(1);
    int len = i->length(1); 
    if (s[pos] != s[pos + len -1]) {
        best = min(len-2, best);
    }
}   

可运行的：https://ideone.com/2UdRGG

- DAle