把字串中重複出現的字元去掉,只留第一次出現的那個,是練習演算法與資料結構的經典小題。雖然實務上機會不多,但它很適合拿來熟悉「以空間換時間」的雜湊思路。
核心想法是邊掃描邊記錄。準備一個物件當成雜湊表,走訪字串的每個字元,若沒見過就記下並收集起來,見過就跳過。
function dropRepeat(str) {
var result = "";
var hash = {};
for (var i = 0; i < str.length; i++) {
var elem = str[i];
if (!hash[elem]) {
hash[elem] = true;
result += elem;
}
}
return result;
}
使用方式:
dropRepeat("abcdd"); // "abcd"
dropRepeat("aabbccabc"); // "abc"
時間複雜度是 O(n),額外使用了 O(k) 的空間(k 為不同字元數)。相比用 indexOf 暴力查找的 O(n²) 寫法,資料量一大差異就很明顯。
若使用 ES6,可以寫得更簡潔:
const dropRepeat = str => [...new Set(str)].join("");
// 或者保留原順序的 reduce 寫法
const dropRepeat2 = str =>
[...str].filter((c, i) => str.indexOf(c) === i).join("");
Set 的底層同樣是雜湊,且天生去重,程式碼短很多。要注意 Set 會連帶改變型別判斷規則(例如 1 與 "1" 視為不同元素),對純字元處理沒有影響。
Python 有個很漂亮的寫法,利用 enumerate 搭配 index:只保留「第一次出現位置等於目前索引」的字元。
# -*- encoding:utf-8 -*-
string = 'abc123456ab2s'
r = ''.join(x for i, x in enumerate(string) if string.index(x) == i)
print string
print r
輸出結果:
abc123456ab2s
abc123456s
這個寫法直覺好讀,但 string.index 每次都要重新搜尋,整體仍是 O(n²)。若要處理大量資料,改用集合會快得多:
seen = set()
r = ''.join(c for c in string if not (c in seen or seen.add(c)))
無論哪種語言,解這類問題的關鍵都在於「如何快速判斷某元素是否已出現」。用陣列的 indexOf 是線性搜尋,用雜湊表或集合則接近常數時間。這正是雜湊結構最典型的價值所在。