Вхождение подпоследовательности в строку

Question

Если даны 2 строки, такие как bangalore и blr, вернуть, если одна появляется в качестве подпоследовательности другой.Вышеприведенный случай возвращает 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;
}

Answer 2

// Solution 1
public static boolean isSubSequence(String str1, String str2) {
     int i = 0;
        int j = 0;
        while (i < str1.length() && j < str2.length()) {
            if (str1.charAt(i) == str2.charAt(j)) {
                i++;
                j++;
            } else {
                i++;
            }
        }
    return j == str2.length();
}

// Solution 2 using String indexOf method
public static boolean isSubSequenceUsingIndexOf(String mainStr, String subStr) {
    int i = 0;
    int index = 0;
    while(i<subStr.length()) {
        char c = subStr.charAt(i);
        if((index = mainStr.indexOf(c, index)) == -1) {
            return false;
        }
        i++;
    }

    return true;
}

Answer 3

O (N) решение, где N - длина подстроки.

bool subsequence( string s1, string s2 ){
    int n1 = s1.length();
    int n2 = s2.length();

    if( n1 > n2 ){
        return false;
    }

    int i = 0;
    int j = 0;
    while( i < n1 && j < n2 ){
        if( s1[i] == s2[j] ){
            i++;
        } 
        j++;
    }

    return i == n1;
}

Answer 4

Найти длину самой длинной общей подпоследовательности .Если она равна длине маленькой строки, вернуть true