' '
, 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
.题目关键是要求出每一个word的 长度,一个word里面没有空格,可以使用slow 和fast两个指针来确定一个word,每次碰到一个word就更新长度,直到扫描到string的最后。碰到一个word的条件: fast - slow > 0 这样才能更新len
solution 1:
class Solution {
public:
int lengthOfLastWord(string s) {
//sanity check
if (s.size() == 0) return 0;
int slow = 0;
int fast = 0;
int len = 0;
s += " ";
//everytime when meet a word, update the len of the word
for (; fast < s.size(); fast++) {
if (s[fast] == ' ') {
if (fast - slow > 0) len = fast-slow; //update len if meet a word
slow = fast + 1;
}
}
return len;
}
};
solution 2:
class Solution {
public:
int lengthOfLastWord(string s) {
//sanity check
if (s.size() == 0) return 0;
int slow = 0;
int fast = 0;
int len = 0;
//everytime when meet a word, update the len of the word
for (; fast < s.size(); fast++) {
if (s[fast] == ' ') {
slow = fast + 1;
} else {
len = fast - slow + 1;
}
}
return len;
}
};
solution1 是当碰到一个可能单词的时候更新len,标志是fast走到了一个空格,但是这样做前提必须在原string后面加上”“,以防止最后一个word不能检测出来。
solution2 是每次fast 和slow相差>0时更新len,此时可能fast 和 slow之间并不是一个word,但是通过每次更新可以将所有word的长度找出来,这种方法是不需要对原字符串进行处理的。所有solution2效率更高。
slow 和 fast指针处理的题目可能有很多种途径得到solution,但是有些solution就很简单高效。
No comments:
Post a Comment