字符串中出现子序列 [英] Sub sequence occurrence in a string

问题描述

给出2个类似bangalore和blr的字符串，返回一个字符串是否显示为另一个字符串的子序列。上面的情况返回true，而bangalore和brl返回false。

Given 2 strings like bangalore and blr, return whether one appears as a subsequence of the other. The above case returns true whereas bangalore and brl returns false.

推荐答案

贪婪策略应该可以解决此问题。

Greedy strategy should work for this problem.

• 在大字符串（* b * angalore）中查找可疑子字符串（blr）的首字母


• 查找第二个字母从第一个字母的索引加一个（anga * l * ore）开始


• 查找第二个字母，从第二个字母的索引加一个（o * r * e）


• 继续，直到您不再在字符串中找到下一个blr字母（不匹配），或者子序列中的字母用完（您有匹配项）为止。 / li>
  

• Find the first letter of the suspected substring (blr) in the big string (*b*angalore)
• Find the second letter starting at the index of the first letter plus one (anga*l*ore)
• Find the third letter starting at the index of the second letter plus one (o*r*e)
• Continue until you can no longer find the next letter of blr in the string (no match), or you run out of letters in the subsequence (you have a match).

以下是C ++中的示例代码：

Here is a sample code in C++:

#include <iostream>
#include <string>
using namespace std;

int main() {
    string txt = "quick brown fox jumps over the lazy dog";
    string s = "brownfoxzdog";
    int pos = -1;
    bool ok = true;
    for (int i = 0 ; ok && i != s.size() ; i++) {
        ok = (pos = txt.find(s[i], pos+1)) != string::npos;
    }
    cerr << (ok ? "Found" : "Not found") << endl;
    return 0;
}

这篇关于字符串中出现子序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！