This post is completed by 1 user

  • 0
 Add to List
Beginner

480. Check if one string is a subsequence of another string.

Objective: Given two strings, write a program to check if any of the given string is a subsequence of another string. Example if given strings are A and B then EITHER A is subsequence of B OR B is subsequence of A, program should return true.

Example:

A = "horizon"
B = "abhordizaonr"
Output: true

A = "abhordizaonr"
B = "horizon"
Output: true

A = "abhor dizaonr"
B = "horizon"
Output: true

A = "abordizaonr"
B = "horizon"
Output: false

Approach: 

  • Given strings, A and B.
  • Check if any of the string is null, return false.
  • Compare the lengths of both the strings 
    • do String longer = A or B, whichever is longer than other.
    • do String shorter = A or B, whichever is shorter than other.
  • Now have two strings, longer and shorter. We know only a shorter string can be a subsequence of a longer string, whereas vice versa is not true.
  • Initialize the starting index for the shorter string as j = 0.
  • Iterate the longer string and for current index i
    • If the character at index i in longer is the same as the character at index j in shorter. If yes then do j++.
  • After iteration, if j==length of shorter means is subsequence in longer string, return true else return false. 

Output:

true
true

Related Problems: