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
.
思路:
一些想法:首先可以用strlen走一遍字符串,直到碰到\0结束符号,然后从字符串的最后一个非空格字符向前回退,直到碰到空格或者字符串的开头。这样最坏情况下时间复杂度是O(2n)。
还有一种方法,只需要遍历一遍字符串。用两个int记录:之前一个word的长度,以及现在正在遍历的word的长度。只要碰到空格,就将当前word的长度保存给前一个word的长度,然后清零当前word的长度。不过这时需要考虑碰到连续几个空格的情况。这样最坏时间复杂度为O(n),减少了一次遍历。
题解:
class Solution { public: int lengthOfLastWord(const char *s) { int last_word_length=0; int this_word_length=0; const char* p=s; while(*p!=0) { if (*p++ == 32 ) { if (this_word_length != 0) last_word_length = this_word_length; this_word_length = 0; } else ++this_word_length; } if (this_word_length == 0) return last_word_length; else return this_word_length; } };