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.

分析

模拟。先从右到左找到第一个字母，然后从右到左找到第一个非字母，二者的距离就是最后一个word的长度。

代码

  1. // Length of Last Word
  2. // 偷懒，用 STL
  3. // 时间复杂度O(n)，空间复杂度O(1)
  4. public class Solution {
  5.     public int lengthOfLastWord(String s) {
  6.         final Predicate isAlphabet = new Predicate() {
  7.             @Override
  8.             public boolean apply(char ch) {
  9.                 return Character.isAlphabetic(ch);
  10.             }
  11.         };
  12.         final Predicate isNotAlphabet = new Predicate() {
  13.             @Override
  14.             public boolean apply(char ch) {
  15.                 return !Character.isAlphabetic(ch);
  16.             }
  17.         };
  18.         int j = findIf(s, s.length() - 1, isAlphabet);
  19.         int i = findIf(s, j, isNotAlphabet);
  20.         return j - i;
  21.     }
  23.     interface Predicate {
  24.         boolean apply(char ch);
  25.     }
  26.     // from right to left
  27.     private static int findIf(final String s, int fromIndex, Predicate p) {
  28.         for (int i = fromIndex; i >= 0; --i) {
  29.             if (p.apply(s.charAt(i))) return i;
  30.         }
  31.         return -1;
  32.     }
  33. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/string/length-of-last-word.html