[Leetcode] 58. Length of Last Word

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.

Example 1:
Input: s = “Hello World”
Output: 5
Explanation: The last word is “World” with length 5.

Example 2:
Input: s = “ fly me to the moon “
Output: 4
Explanation: The last word is “moon” with length 4.

Example 3:
Input: s = “luffy is still joyboy”
Output: 6
Explanation: The last word is “joyboy” with length 6.

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

最后一个单词的长度。

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。 单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

思路一

因为 input 字符串里有空格，所以可以将 string 根据空格分割成 string array。分割后直接看 string array 中最后一个单词的长度。

复杂度

时间O(n)
空间O(n)

代码

Java实现

// O(n) space, O(n) time
class Solution {
    public int lengthOfLastWord(String s) {
		// corner case
		if (s == null || s.length() == 0) {
			return 0;
		}

		// normal case
		String[] words = s.split(" ");
		int n = words.length;
		String last = words[n - 1];
		return last.length();
    }
}

思路二

不使用额外空间，从后往前扫描 input 字符串，遇到第一个空格就停下，此时停下的位置到字符串末尾的距离就是最后一个单词的长度。

复杂度

时间O(n)
空间O(1)

代码

Java实现

// O(1) space, O(n) time
class Solution {
    public int lengthOfLastWord(String s) {
        // corner case
        if (s == null || s.length() == 0) {
            return 0;
        }

        // normal case
        s = s.trim();
        int n = s.length();
        int count = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) != ' ') {
                count++;
            } else {
                break;
            }
        }
        return count;
    }
}

JavaScript实现

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLastWord = function (s) {
    // corner case
    if (s === null || s.length === 0) {
        return 0;
    }

    // normal case
    let input = s.trim();
    let count = 0;
    for (let i = input.length - 1; i >= 0; i--) {
        if (input[i] !== ' ') {
            count++;
        } else {
            break;
        }
    }
    return count;
};