In this tutorial, I am going to discuss a problem Is Subsequence (check if a string is subsequence of another string).
Given two strings str1 and str2, check if str1 is a subsequence of str2. Both strings consists only of lowercase characters.
Example 1:
Input: str1 = “abc”, str2 = “ahbgdc”
Output: true
Example 2:
Input: s = “axc”, t = “ahbgdc”
Output: false
What is Subsequence?
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
For example : abd is a subsequence of abcde.
In this tutorial, I am going to discuss iterative and recursive approach to solve this problem.
Data Structure Video Tutorials
Programming Questions on Arrays
Programming Questions on Linked List
Programming Questions on Binary Tree
Check If a String is Subsequence of Another String (Is Subsequence) – Two Pointers
In this example, we are going to solve this problem using two pointers.
Take two pointers sIndex and tIndex. The pointer sIndex points to String str1 and pointer tIndex points to string str2. The initial value is zero for both the pointers.
Then compare the character present at both the indexes. If it is equal then increment the value of both the pointers. Else increment the value of pointer which points to String str2.
If all the characters of string str1 is present in string str2 it means the value of sIndex is equal to s.length.
The time complexity of this approach is O(n), where n is the length of string s. It’s space complexity is O(1).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
//Check If a String is Subsequence of Another String - Java Code public boolean isSubsequence(String s, String t) { int sLen = s.length(); int tLen = t.length(); if (sLen == 0) return true; int sIndex = 0; int tIndex = 0; while (sIndex < sLen && tIndex < tLen) { if (s.charAt(sIndex) == t.charAt(tIndex)) sIndex++; tIndex++; } return sIndex == sLen; } |
Check whether two strings are anagrams of each other
Check If a String is Subsequence of Another String using Recursion – Java Code
We have written an iterative code to solve this problem. Let’s write it’s recursive version.
The time complexity and space complexity of this approach is O(n), where n is the length of string s.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
//Is Subsequence - Recursive code public boolean isSubsequenceRecursive(String s, String t) { return subsequenceHelper(s, t, 0, 0); } public boolean subsequenceHelper(String s, String t, int sIndex, int tIndex) { if (s.length() == sIndex) { return true; } if (t.length() == tIndex) { return false; } return s.charAt(sIndex) == t.charAt(tIndex) ? subsequenceHelper(s, t, sIndex + 1, tIndex + 1) : subsequenceHelper(s, t, sIndex, tIndex + 1); } |
