Create an account


Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
[Tut] How To Check if One String is a Subsequence of Another?

#1
How To Check if One String is a Subsequence of Another?

Problem Formulation


Description

Given two strings str1 and str2, check if str1 is a subsequence of str2.

subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

constraints:

  • 0 <= str1.length <= 100
  • 0 <= str2.length <= 104
  • str1 and str2 consist only of lowercase English letters.

Example 1:

Input: str1 = "abc", str2 = "ahbgdc"
Output: true

Example 2:

Input: str1 = "axc", str2 = "ahbgdc"
Output: false

? Companies that asked this problem: Accolite, Tesco, Google

Solution


def isSubSequence(str1, str2): len_str1 = len(str1) len_str2 = len(str2) index_str1 = 0 # Index of str1 index_str2 = 0 # Index of str2 # Traverse both str1 and str2 while index_str1 < len_str1 and index_str2 < len_str2: # Compare current character of str2 with if str1[index_str1] == str2[index_str2]: # If matched, then move to next character in str1 index_str1 = index_str1 + 1 index_str2 = index_str2 + 1 # If all characters of str1 matched, # then j is equal to m return index_str1 == len_str1 val_1 = 'abc'
val_2 = 'ahbgdc'
print(isSubSequence(val_1, val_2))

Output:

True

Explanation:

  • len_str1 and len_str2 store the length of str1 and str2 respectively.
  • index_str1 and index_str2 are used to store the indices of each character of str1 and str1 respectively.
  • The while loop is used to traverse through the strings until a match is found or all the indices of str2 have been traversed in case of no match.
    • The if statement compares the current character of str1 and str2.
      • In case a match is found, the index of the next character in str2 is taken into account.
    • The value of index_str1 is incremented at every iteration to traverse through all the letters available in str1 until the subsequence is found.
  • Finally, if the subsequence was found the value stored by index_str1 will be equal to the length of str1.

Dry Run:

The following table illustrates the operation at each iteration within the while loop until the match is found.


? Video Solution


The post How To Check if One String is a Subsequence of Another? first appeared on Finxter.



https://www.sickgaming.net/blog/2021/04/...f-another/
Reply



Possibly Related Threads…
Thread Author Replies Views Last Post
  [Tut] How to Check the Pandas Version in Your Script? xSicKxBot 0 8 Yesterday, 08:38 PM
Last Post: xSicKxBot
  [Tut] How to Check if the Current Time is in a Range in Python? xSicKxBot 0 18 05-10-2021, 02:53 PM
Last Post: xSicKxBot
  [Tut] Python Regex to Return String Between Parentheses xSicKxBot 0 22 05-04-2021, 05:21 PM
Last Post: xSicKxBot
  [Tut] Converting Integer to String in Python xSicKxBot 0 39 04-18-2021, 11:56 AM
Last Post: xSicKxBot
  [Tut] How To Remove All Non-Alphabet Characters From A String? xSicKxBot 0 34 04-17-2021, 09:56 PM
Last Post: xSicKxBot
  [Tut] How to Check if a Python String Contains Only Digits? xSicKxBot 0 40 04-12-2021, 12:23 PM
Last Post: xSicKxBot
  [Tut] How to Convert a String List to an Integer List in Python xSicKxBot 0 43 04-09-2021, 01:50 PM
Last Post: xSicKxBot
  [Tut] How to Convert a Float List to a String List in Python xSicKxBot 0 42 04-07-2021, 02:53 PM
Last Post: xSicKxBot
  [Tut] Python – How to Check if a Dict Key Exists? xSicKxBot 0 37 04-03-2021, 11:11 AM
Last Post: xSicKxBot
  [Tut] Python String to Float Conversion xSicKxBot 0 42 04-01-2021, 11:07 PM
Last Post: xSicKxBot

Forum Jump:

[-]
Active Threads
(Indie Deal) God Eater 3, DRAGON BALL, T...
Last Post: xSicKxBot
Today 10:20 AM
» Replies: 0
» Views: 6
Microsoft - Making remote and hybrid mee...
Last Post: xSicKxBot
Today 05:33 AM
» Replies: 0
» Views: 7
News - JAVA EDITION: SNAPSHOT 21W19A
Last Post: xSicKxBot
Today 05:31 AM
» Replies: 0
» Views: 7
News - Koei Tecmo’s Guzzler Joins Hamste...
Last Post: xSicKxBot
Today 05:30 AM
» Replies: 0
» Views: 8
News - Sega Looking To Release Brand New...
Last Post: xSicKxBot
Today 05:30 AM
» Replies: 0
» Views: 7
Xbox Wire - Xbox Spotlight: Mental Healt...
Last Post: xSicKxBot
Today 05:30 AM
» Replies: 0
» Views: 7
News - Live services push EA to $6.19 bi...
Last Post: xSicKxBot
Today 05:29 AM
» Replies: 0
» Views: 44
News - Blog: Improving the ‘About This G...
Last Post: xSicKxBot
Today 05:29 AM
» Replies: 0
» Views: 36
[Tut] How to Check the Pandas Version in...
Last Post: xSicKxBot
Yesterday 08:38 PM
» Replies: 0
» Views: 8
(Indie Deal) NBA 2K21, MY HERO ONE'S JUS...
Last Post: xSicKxBot
Yesterday 08:37 PM
» Replies: 0
» Views: 6

[-]
Twitter

Copyright © SickGaming.net 2012-2020