58 Length of Last Word

---

title: Length of Last Word
tags:
- length-of-last-word
- No.58
- simple
- finite-automata
- string

---

Problem

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.

Example:

Input: "Hello World"
Output: 5

Corner Cases

• begin with " "
• end with " "
• empty string ""
• single word "a"

Solutions

Finite Automata

Use finite automata to solve this problem. The transition table is:

state	" "	"\w"
0	1(l=0)	2(l++)
1	1(l=0)	2(l++)
2	1(l=0)	2(l++)

But this table cannot deal with strings ending with " ", thus we should adjust the ending index, like String.rstrip() in python and String.trim() in java.

The running time is O(n).

class Solution {
    public int lengthOfLastWord(String s) {
        if (s.equals("")) {return 0;}

        int[][] dfa = new int[3][2];
        for (int i=0; i<3; i++) {
            dfa[i][0] = 1;
            dfa[i][1] = 2;
        }

        String[] t = s.split("");
        int      e = t.length - 1;
        while (t[e].equals(" ")) {
            e--;
            if (e < 0) {break;}
        }

        int l = 0;
        int j = 0;
        for (int i=0; i<=e; i++) {
            j = dfa[j][f(t[i])];
            l = (j == 2) ? l + 1 : 0;
        }
        return l;
    }

    private int f(String x) {
        return (x.equals(" ") ? 0 : 1);
    }
}