Sequence in string

Question

Given 2 lines, such as bangalore and blr, return whether it will be displayed as a subsequence of the other. The above case returns true, while bangalore and brl returns false.

Answer 1

A greedy strategy should work on this issue.

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

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; } 

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), where N is the length of the substring.

 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

Find the length of the longest common subsequence . If it is equal to the length of the small string, return true