Using C++ to check if string s is subsequence of string t The problem I want to solve is very simple:


  Given a string s and a string t, check if s is subsequence of t. there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (&lt;=100).
  
  Example 1:
  s = "abc", t = "ahbgdc"
  Return true.
  
  Example 2:
  s = "axc", t = "ahbgdc"
  Return false.


I only learnt C++ for about 30 hours, so I am not sure whether my below solution is correct C++ style or not, especially when to free the pointer allocated space. I assigned two char pointer to each string and I do know I need to free them somewhere else. Since the return value depends on pointer, I don't know where to free the pointer allocated memory, which should be a big deal.

What I thought about this question is that there must be two pointers, each pointing one string. For these two strings, using pointers to compare character one by one.

#include &lt;iostream&gt;
#include &lt;string.h&gt;

using namespace std;

class Solution {
public:
bool isSubsequence(string s, string t) {
    char *sPtr = new char[s.size() + 1];
    char *tPtr = new char[t.size() + 1];

    bool returnVal = false;

    strcpy(sPtr, s.c_str());
    strcpy(tPtr, t.c_str());

    while (*sPtr &amp;&amp; *tPtr){
        if (*sPtr == *tPtr++) {
            sPtr++;
        }
    }

    return !*sPtr;

   }
};

int main() {

    string s = "abc";
    string t = "ahbgdc";

    Solution sol = Solution();
    cout &lt;&lt; sol.isSubsequence(s, t)&lt;&lt;endl;

    return 0;
}


After I talked to one of classmates, he suggests that to include  and use c++ string class to do this question. Following is my solution followed his suggestion, but for my above solution, he just said "I don't know dude, I just use c++ string class, that's simple. Your solution is just weird to me but I don't know why I feel weird."

class Solution {
public:
    bool isSubsequence(string s, string t) {
    int sIndex = 0;
    int tIndex = 0;

    while (sIndex &lt; s.size() &amp;&amp; tIndex &lt; t.size()) {
        if (s[sIndex] == t[tIndex++]) {
            sIndex++;
        }
    }

    return sIndex &gt;= s.size();
    }

};
using namespace std is considered bad practice.  Also, in C++, you should #include &lt;string&gt; rather than #include &lt;string.h&gt;.

The Solution class is an unnecessary complication.  You would be better off with just an isSubsequence() function.

In your first function, returnVal is never used.  Compiling with warnings enabled should alert you to the dead code.

The memory management rule is simple: every new must be paired with exactly one delete, and every new something[] must be paired with exactly one delete[].  Since the first solution calls new[] twice with no delete[], you have a memory leak.  Your friend is right: you should take advantage of the string class, because the whole point of the string class is to take care of memory management for you.  The second solution is definitely better.

The function signature is not ideal.  Having string parameters will cause each string to be needlessly copied when the function is called.  You should write instead:

bool isSubsequence(const std::string &amp;s, const std::string &amp;t) {
    …
}


std::string::size() returns std::string::size_type, so strictly speaking, you should use std::string::size_type instead of int.  (Or, if using c++11, just use auto.)