LeetCode 58. Length of Last Word

はじめに

LeetCode 「58. Length of Last Word」の問題をGoで解きました。

問題

https://leetcode.com/problems/length-of-last-word/description

問題文

Given a string s consisting of words and spaces, return the length of the last word in the string.
A word is a maximal substring* consisting of non-space characters only.

*A substring is a contiguous non-empty sequence of characters within a string.

和訳
単語とスペースからなる文字列 s が与えられた場合、文字列の最後の単語の長さを返します。
単語とは、スペース以外の文字のみで構成される最大部分文字列*です。

*部分文字列とは、文字列内の連続した空でない文字の並びのことです。

例

Input: s = "Hello World"
Output: 5
Explanation: The last word is "World" with length 5.

Input: s = "   fly me   to   the moon  "
Output: 4
Explanation: The last word is "moon" with length 4.

Input: s = "luffy is still joyboy"
Output: 6
Explanation: The last word is "joyboy" with length 6.

制約

• 1 <= s.length <= 104
• s consists of only English letters and spaces ' '.
• There will be at least one word in s.

解答

最後の単語の長さだけわかればいいので、後ろから走査することで効率的に実装できそうです。
最初に文字を見つけたらカウントを開始し、次にスペースあるいは文字列の先頭が来たらカウントを終了するというアプローチを取ります。

コード

func lengthOfLastWord(s string) int {
    length := 0
    n := len(s)

    // 末尾の空白を飛ばす
    for n > 0 && s[n-1] == ' ' {
        n--
    }

    // 最後の単語の長さを数える
    for n > 0 && s[n-1] != ' ' {
        length++
        n--
    }

    return length
}

計算量

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