Sunday, October 30, 2016

LeetCode OJ - Is Subsequence

Problem:

Please find the problem here.

Analysis:

A greedy strategy would work, if 'aS' is a subsequence of 'BaC' where B does not contain any occurrence of 'a', then S must be a subsequence of C.

Solution: 

We will simply march two strings with two pointers and advance the one pointing to s whenever we see a match.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/is-subsequence/

#include "LEET_IS_SUBSEQUENCE.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_IS_SUBSEQUENCE
{
    class Solution
    {
    public:
        bool isSubsequence(string s, string t)
        {
            if (s == "")
            {
                return true;
            }
            int i = 0;
            for (int j = 0; j < t.length(); j++)
            {
                if (t[j] == s[i])
                {
                    i++;
                    if (i == s.length())
                    {
                        return true;
                    }
                }
            }

            return false;
        }
    };
};

using namespace _LEET_IS_SUBSEQUENCE;

int LEET_IS_SUBSEQUENCE()
{
    Solution solution;
    cout << solution.isSubsequence("abc", "ahbgdc") << endl;
    return 0;
}

No comments :

Post a Comment