POJ 1035 Spell Checker：編輯距離為1的單詞糾錯

問題描述

給定字典和待檢查單詞列表。對每個待檢查單詞：
- 若在字典中 → "word is correct"
- 否則找出字典中通過單次編輯可得到的單詞：
1. 替換一個字符（長度相同，僅一處不同）
2. 刪除一個字符（字典詞比輸入短1，其餘相同）
3. 插入一個字符（字典詞比輸入長1，其餘相同）
- 按字典順序輸出匹配詞，無則只輸入"word:"

Java實現核心邏輯

三種編輯操作判斷

// 替換：長度相同，最多一個字符不同
boolean replace(char[] input, char[] dict) {
    if(input.length != dict.length) return false;
    int diff = 0;
    for(int i=0; i 1) return false;
    return true;
}

// 刪除：輸入比字典長1，刪除一字符後匹配
boolean delete(char[] input, char[] dict) {
    if(input.length - dict.length != 1) return false;
    int diff = 0, i=0, j=0;
    while(i < input.length && j < dict.length) {
        if(input[i] != dict[j]) {
            if(++diff > 1) return false;
            i++; // 跳過輸入中的多出字符
        } else { i++; j++; }
    }
    return true;
}

// 插入：輸入比字典短1，插入一字符後匹配
boolean add(char[] input, char[] dict) {
    if(dict.length - input.length != 1) return false;
    int diff = 0, i=0, j=0;
    while(i < input.length && j < dict.length) {
        if(input[i] != dict[j]) {
            if(++diff > 1) return false;
            j++; // 跳過字典中的多出字符
        } else { i++; j++; }
    }
    return true;
}

主流程

// 讀取字典（以#分隔）
// 讀取待檢查詞（以#結束）

for(String input : inputList) {
    if(dictionary.contains(input)) {
        System.out.println(input + " is correct");
    } else {
        StringBuilder sb = new StringBuilder(input + ":");
        for(String dict : dictionary) {
            if(replace(input, dict) || delete(input, dict) || add(input, dict))
                sb.append(" ").append(dict);
        }
        System.out.println(sb.toString());
    }
}

關鍵細節

• 輸入以#為分隔符，兩個#之間為字典，第二個#後為待檢查詞
• 字典和待檢查詞均用List保持順序
• 編輯距離判斷優化：先比長度，再雙指針掃描
• 輸出格式："word:"或"word: dict1 dict2..."

複雜度

設字典大小D，待檢查詞Q，平均長度L。
時間：O(Q × D × L) — 數據規模小（POJ 1035）可接受。
大規模場景可用Trie或BK-tree優化。