LeetCode 392. Is Subsequence

はじめに

LeetCode 「392. Is Subsequence」の問題をGoで解きました。

問題

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

問題文

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

和訳
2つの文字列 sと tが与えられたとき、sが tの部分文字列であれば真を、そうでなければ偽を返す。

文字列の部分列とは、元の文字列から、残りの文字の相対的な位置を乱すことなく、文字の一部（なくてもよい）を削除してできた新しい文字列のことである。（すなわち、"ace" は "abcde" の部分文字列であるが、"aec" はそうではない）

例

Input: s = "abc", t = "ahbgdc"
Output: true

Input: s = "axc", t = "ahbgdc"
Output: false

制約

• 0 <= s.length <= 100
• 0 <= t.length <= 104
• s and t consist only of lowercase English letters.

解答1

tの中でsが順番通りに存在すれば真と判定します。
tを先頭から捜査しながら、sと同じ文字があればsを捜査するポインタ動かすことで解くことができます。

コード

func isSubsequence(s string, t string) bool {
    sPointer := 0
    sLength := len(s)

    if sLength == 0 {
        return true
    }

    for i := 0; i < len(t); i++ {
        if t[i] == s[sPointer] {
            sPointer++
            if sPointer == sLength {
                return true
            }
        }
    }

    return false
}

sが長さ0の場合があるので、最初のif文でそれに該当すればtrueを返すようにしています。

計算量

• 時間的計算量：O(n)
• 空間的計算量：O(1)

解答2

解答1をより簡潔に書くことができます。
よりTwo Pointersパターンっぽい書き方です。

コード

func isSubsequence(s string, t string) bool {
    i, j := 0, 0

    for i < len(s) && j < len(t) {
        if s[i] == t[j] {
            i++
        }
        j++
    }

    return i == len(s)
}

計算量

• 時間的計算量：O(n)
• 空間的計算量：O(1)