單詞計數器：有限狀態機在字串處理中的經典應用

問題背景

面試高頻題：統計由字母與空格組成的字串中有多少個單詞。核心考察點在於有限狀態機（FSM）的設計與實現能力。

狀態機建模

定義三種狀態：

狀態轉移圖

          輸入字符                輸入空格
    INIT ──────────▶ WORD ──────────▶ SPACE
     ▲                │                │
     │                ▼                ▼
     └──────────── END ◀──────────────┘

• INIT：遇字符→WORD（計數+1），遇空格→SPACE，遇結束→返回。
• WORD：遇字符→保持，遇空格→SPACE，遇結束→返回計數。
• SPACE：遇空格→保持，遇字符→WORD（計數+1），遇結束→返回計數。

C 語言實現

#include <stdio.h>
#include <assert.h>

typedef enum {
    INIT_STATE  = 1,
    WORD_STATE,
    SPACE_STATE
} State;

int count_word_number(const char* pStr) {
    if (NULL == pStr) return 0;

    int count = 0;
    State state = INIT_STATE;
    char ch;

    while ((ch = *pStr++) != '\0') {
        switch (state) {
            case INIT_STATE:
                if (ch != ' ') {
                    ++count;
                    state = WORD_STATE;
                } else {
                    state = SPACE_STATE;
                }
                break;

            case WORD_STATE:
                if (ch == ' ')
                    state = SPACE_STATE;
                // 字符則保持 WORD_STATE
                break;

            case SPACE_STATE:
                if (ch != ' ') {
                    ++count;
                    state = WORD_STATE;
                }
                // 空格則保持 SPACE_STATE
                break;
        }
    }
    return count;
}

測試用例

void test() {
    assert(0 == count_word_number(NULL));
    assert(0 == count_word_number(""));
    assert(1 == count_word_number("hello"));
    assert(3 == count_word_number("china baby hello"));
    assert(2 == count_word_number("  leading spaces"));
    assert(2 == count_word_number("trailing spaces  "));
    assert(3 == count_word_number("multiple   spaces   between"));
    printf("All tests passed!\n");
}

擴展思考

1. 狀態機通用性：此模式廣泛用於詞法分析、協議解析（如 TCP 狀態機）、文本處理。
2. 表驅動實現：對於複雜狀態機，可用二維表 next_state[state][input_type] 替代 switch，便於維護擴展。
3. 邊界條件：空串、純空格、前導/尾隨空格、多重空格均正確處理。

總結

單詞計數雖簡單，卻完美展示了狀態機思維：將問題分解為離散狀態與明確轉移。掌握此法，可輕鬆應對更複雜的字串解析任務。