Monday, December 24, 2012

[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.
» Solve this problem

[解题思路]
这题完全是实现题。没有算法难度。从最后往前扫描。处理如下三种模式:(*表示若干个空格)
1. "*"
2. "*word"
3. "*word*"
4. "word*"

1:    int lengthOfLastWord(const char *s) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      int len = strlen(s);  
5:      if( len== 0) return 0;  
6:      int i = len-1;  
7:      while(s[i] == ' ' && i>=0) i--;  
8:      if(i == -1)   
9:      {  
10:        return 0;  
11:      }  
12:      int end = i;  
13:      for(; i >=0; i--)  
14:      {  
15:        if(s[i] == ' ')  
16:          break;  
17:      }  
18:      if(i ==-1)  
19:        return end+1;  
20:      return end-i;  
21:    }  

[已犯错误]
1. Line 8, 18。 一开始写成i ==0了,当模式2及模式3时就算不对了。

Update 3/15/2013: refactor code

1:       int lengthOfLastWord(const char *s) {  
2:            int len = strlen(s);  
3:            int count = 0;  
4:            for(int i =len-1; i>=0; i--)  
5:            {  
6:                 if(s[i] == ' ')  
7:                 {  
8:                      if(count ==0) continue;  
9:                      else return count;  
10:                 }  
11:                 count++;  
12:            }  
13:            return count;  
14:       }  


Update 4/7/2013:Refactor Code
上面的解法多跑了一趟,没有必要。这一题期待的解法应该是从左到右只扫描一遍。不过上面解法的好处是写起来很简洁、漂亮。。。
1:       int lengthOfLastWord(const char *s) {  
2:            const char *p =s;  
3:            const char *start=p;  
4:            int len=0;  
5:            while(*p!='\0')  
6:            {  
7:                 if(*p == ' ')  
8:                 {  
9:                      len = p - start;  
10:                      while(*p == ' ') p++;  
11:                      start = p;   
12:                      continue;  
13:                 }  
14:                 p++;                 
15:            }  
16:            if(*start !='\0')  
17:                 len = p-start;  
18:            return len;  
19:       }  



Update 08/24/2014 Refactor Code
Another way to track the length of word

1:       int lengthOfLastWord(const char *s) {  
2:            const char* pStart=s;  
3:            const char* pEnd=s;  
4:            const char* p = s;  
5:            const char* pre=s;  
6:            while(*p!='\0')  
7:            {  
8:                 if(*pre == ' ' && *p !=' ') pStart = p;  
9:                 if(*pre != ' ' && *p == ' ') pEnd = p;  
10:                 pre = p;  
11:                 p++;  
12:            }  
13:            if(*pre != ' ' && *p == '\0') pEnd = p;  
14:            return pEnd - pStart;  
15:       }  



1 comment: