算法题--统计字符串中最后一个非空格子串的长度

image.png

0. 链接

题目链接

1. 题目

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word (last word means the last appearing word if we loop from left to right) in the string.

If the last word does not exist, return 0.

Note: A word is defined as a maximal substring consisting of non-space characters only.

Example:

Input: "Hello World"
Output: 5

2. 思路1：从左到右遍历

记录    
        begin_idx = None
        end_idx = None
        started = False

遇到空格时, started=False
遇到非空格时, 
如果started=False
    end_idx=begin_idx=i, started=True
否则
    end_idx=i
    
如果end_idx is None or begin_idx is None:
    返回0
否则:
    返回end_idx - begin_idx + 1

3. 代码

# coding:utf8


class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        begin_idx = None
        end_idx = None
        started = False
        for i in range(len(s)):
            if s[i] == ' ':
                started = False
            elif started:
                end_idx = i
            else:
                started = True
                begin_idx = i
                end_idx = i

        if end_idx is None or begin_idx is None:
            return 0
        else:
            return end_idx - begin_idx + 1


solution = Solution()
print(solution.lengthOfLastWord('Hello World'))
print(solution.lengthOfLastWord('a '))
print(solution.lengthOfLastWord('a'))

输出结果

5
1
1

4. 结果

image.png

5. 思路2：从右往左遍历

记录
    end_idx = None

从右往左遍历
    碰到第一个非空格字符, end_idx = i
    碰到下一个空格字符, 则直接返回end_idx - i
    
遍历完了也没用碰到下一个空格字符, 则返回end_idx + 1

6. 代码:

# coding:utf8


class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        end_idx = None
        for i in range(len(s) - 1, -1, -1):
            if s[i] != ' ':
                if end_idx is None:
                    end_idx = i
            else:
                if end_idx is not None:
                    return end_idx - i

        if end_idx is not None:
            return end_idx + 1
        else:
            return 0

solution = Solution()
print(solution.lengthOfLastWord('Hello World'))
print(solution.lengthOfLastWord('a '))
print(solution.lengthOfLastWord('a'))

输出结果为:

5
1
1

7. 结果

image.png