iT邦幫忙

DAY 27
0

連續30天,挑戰演算法系列 第 27

[Day27] 30 天挑戰演算法 - 最後一個單字長度

題目來源:Length of Last Word

問題:
給予一個有大小寫字母和空白字元的字串 s ,請試著計算該字串中最後一個英文單字的字母個數。
如果最後一個單字不存在則回傳 0

註:單字的定義為不含空白字元的英文字母組成的字串。

例子
給予字串 s = "Hello World.", 則最後一個單字為 world, 請回傳 5

想法
如果還記得前幾天我們做過一題 反轉文字字串,這一題就變得非常簡單。因為可以使用相同的手法來計算出最後一個單字的字母個數。

首先可以先將字串以單字為單位切割成單字陣列(word string array),接著再回傳最後一個單字的長度就可以了!
突然覺得!好簡單阿!

String[] splitedWord = inputword.split("\\s+");

回傳最後一個單字的長度

String lastWord = splitedWord[splitedWord.length-1];
return lastWord.length();

不過,這題只是要我們計算字串中最後一個單字的長度,用上面那個作法空間複雜度太高,總是有種「殺雞用牛刀」的感覺。太浪費了!所以,要換另外一種方式才行!

題目說「單字會用空白隔開」,那我們是不是可以從頭到尾掃一次,遇到空白就重新計算呢?這樣我們的空間複雜度就會從 O(N) 降到 O(1) 了。

public int lengthOfLastWord(String s) {
    int length = 0;
    for (int i=0; i<s.length(); i++) {
        if (s.charAt(i) == ' ')
            length = 0;
        else
            length++;
    }
    return length;
}

寫好了之後,就直接上 Length of Last Word 測試一下看看有沒有問題。
沒想到居然出現了一個問題,也就是當 最後一個單字後面有一個空白,就會導致我們計算的結果為0。
所以是我們少考慮到這一個條件!沒關係,我們只要在計算前把他去掉即可。修改後的答案如下:

public int lengthOfLastWord(String s) {
    int length = 0;
    s = s.trim(); // 去掉字串中最後面的空白字元
    for (int i=0; i<s.length(); i++) {
        if (s.charAt(i) == ' ')
            length = 0;
        else
            length++;
    }
    return length;
}

如此一來我們的時間複雜度為 O(N), 空間複雜度為 O(1)。
不過這方法好像還是不夠好。因為字串又不是 List, 為什麼一定要從最前面開始呢?既然題目都只定要最後一個單字了,我們或許也可以從最後面開始往前推到第一個空白符號,如此一來我們的時間複雜度一定會小於或等於 O(N)。
那這個方式就留給大家去改寫看看囉!


上一篇
[Day26] 30 天挑戰演算法 - 從List的尾巴刪除第N個節點
下一篇
[Day28] 30 天挑戰演算法 - 驗證括號
系列文
連續30天,挑戰演算法30

尚未有邦友留言

立即登入留言