字符串中的子序列出现

Question

给出像bangalore和blr这样的2个字符串,返回一个是否作为另一个的子序列出现.上述情况返回true,而bangalore和brl返回false.

Answer 1

贪婪的策略应该适用于这个问题.

• 在大字符串中找到可疑子串(blr)的第一个字母(*b*angalore)
• 找到从第一个字母的索引加上一个开头的第二个字母(anga*l*ore)
• 找到从第二个字母的索引加上一个开头的第三个字母(o*r*e)
• 继续,直到你再也找不到字符串中的下一个blr字母(不匹配),或者子序列中的字母用完(你有匹配).

以下是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;
}