58. Length Of Last Word

發表於 更新於 分類於 ， 閱讀次數： Disqus： 文章字數： 312

種類 : list
難度 : easy
題目 : 58.Length of Last Word

思維邏輯

  1. 由字串末端向前推進，使用two point
  2. right為字串尾，逐一向左，直至 s[right] != ' '
  3. left隨right向左
  4. 當 s[right] != ' ' 時，left向左，直至left == 0 or s[left] != ' '

解法

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        right = len(s) - 1
        len_w = 0
        while right >= 0:
            left = right
            while left >= 0 and s[left] != ' ':
                len_w += 1
                left -= 1
            if len_w > 0:  return len_w
            right -= 1
        return 1

時間複雜度: O(n)
空間複雜度: O(1)

難點

  1. two point範圍容易搞混，right必須歷遍[0, n]，故為len(s) - 1
  2. left需在字串開頭([0])與值為空的時候停止計算
  3. 避免在迴圈中重複計算單字的長度

最佳解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def twoPoint(self, s: str) -> int:                
        end = len(s) - 1

        while s[end] == " ":
            end -= 1
        
        start = end
        while start >= 0 and s[start] != " ":
            start -= 1
        
        return end - start

    def pythonFunction(self, s: str) -> int:
        words = s.strip().split()
        
        if not words:
            return 0
        
        return len(words[-1])

時間複雜度: O(n)
twoPoint將兩point的loop分開(因left point無需逐一歷遍)，與自身解法相比下，更簡單易懂，也避免第一層迴圈中len_w已經計算好要跳出迴圈的問題。
pythonFunction()使用python內建函數，與演算法無關，但最簡易。