GoLang Function to Check if a String is a Subsequence of Another

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A 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).

Example 1:
Input: s = “abc”, t = “ahbgdc”
Output: true

Example 2:

Input: s = “axc”, t = “ahbgdc”
Output: false

Is Subsequence Algorithm in GoLang

Two Pointers, moving both pointers i and j if the s[i] is equal to t[j]. Otherwise, only move pointer j until j reaches the end.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

func isSubsequence(s string, t string) bool {
    var ls, lt = len(s), len(t)
    if ls > lt {
        return false
    }
    var i, j = 0, 0
    for i < ls && j < lt {
        if s[i] == t[j] {
            i += 1
        }
        j += 1
    }
    return i == ls
}

func isSubsequence(s string, t string) bool {
    var ls, lt = len(s), len(t)
    if ls > lt {
        return false
    }
    var i, j = 0, 0
    for i < ls && j < lt {
        if s[i] == t[j] {
            i += 1
        }
        j += 1
    }
    return i == ls
}

Assuming length of s is smaller than t – the time complexity is O(N) where N is the number of strings in t. The space complexity is O(1).

String Subsequence Algorithms:

• Teaching Kids Programming – Is Subsequence Algorithm via Recursion (Greedy)
• Teaching Kids Programming – Is Subsequence Algorithm via Two Pointer
• The Subsequence Algorithm for Two Strings – How to Check if a String is Subsequence of Another?
• GoLang Function of Checking Is Subsequence
• Algorithms to Check if a String is a Subsequence String of Another String
• in Python, you can do this in Pythonic way: Python Function to Check Subsequence

–EOF (The Ultimate Computing & Technology Blog) —