Saturday, November 22, 2014

[LeetCode] Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.
If the last word does not exist, return 0.
Note: A word is defined as a character sequence consists of non-space characters only.
For example,
Given s = "Hello World",
return 5.

思路:

首先想到的是找到s的尾部,然后反向扫最后一个word得到长度。但这样扫需要两个pass,效率还不是最优,目标是一个pass解决。

用两个变量lastLen, curLen分别记录前一个和当前word的长度。
1. 当前字符为字母时,说明当前word仍然没结束,更新curLen++
2. 当前字符为空格时,如果curLen不为0,说明是一个word刚结束,将lastLen更新为curLen。
3. 当前字符为空格且curLen=0,说明前一个字符也是空格,不需要额外操作。
4. 由于只有在遇到空格时才更新lastLen,当最后一个word后没有空格就结束时,lastLen还没有被更新,所以在搜索完整个s后,如果curLen不为0,则curLen才是真正最后word的长度。而如果最后一个word后有空格,则lastLen为长度。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int lengthOfLastWord(const char *s) {
        int lastLen = 0, curLen = 0;
        while(*s) {
            if(isalpha(*s))
                curLen++;
            else if(curLen!=0) {
                lastLen = curLen;
                curLen = 0;
            }
            s++;
        }
        return curLen==0? lastLen : curLen;
    }
};

No comments:

Post a Comment