我雖然反對在軟體工程師面試時考白板題,不過對於 Leetcode 的態度就沒這麼反對。
偶爾會解一下 Leetcode Daily 作為工作前的醒腦準備,也不失為一種生活樂趣。
題目
318. Maximum Product of Word Lengths
從範例中不難看出,本題需要的工作有兩個:
- 找出兩個使用不重複字母的字串
- 上述兩個字串的長度之乘積
- 找出乘積的最大值,即為解答
解題思路
本題最核心的問題應該是:如何驗證兩個字串是否使用了相同的字元。
假設當前存在兩個字串 abc
與 def
,我們嘗試將其轉變為以下形式:
a b c d e f
1 1 1 0 0 0 (abc) = 56
0 0 0 1 1 1 (def) = 7
根據使用的字元,將其安排一個 bit 做記錄,這麼一來便可以得到兩個整數(abc = 56
、def = 7
),只要將這兩個值做一次 &
如果為 0
表示使用的字元沒有重複。
如此一來,整個實作如下
#define MAX(a, b) ((a) > (b) ? (a) : (b))
uint32_t to_bin(char *str) {
int ret = 0;
while (*str)
ret |= 1 << *str++ - 'a';
return ret;
}
int maxProduct(char ** words, int wordsSize) {
int ans = 0;
for (int i = 0; i < wordsSize-1; i++) {
for (int j = i+1; j < wordsSize; j++) {
int product = strlen(words[i]) * strlen(words[j]);
if (product < ans) continue;
if (to_bin(words[i]) & to_bin(words[j])) continue;
ans = MAX(ans, product);
}
}
return ans;
}
to_bin(char *str)
的目的是將字串依規則轉為整數,因為有 26 個字母所以需要至少 26 bits,這邊直接使用uint32_t
優化
重複計算的 words[i]
顯而易見地,words[i]
在第二個迴圈中被重複呼叫 to_bin()
,這不利於效能。
int maxProduct(char ** words, int wordsSize) {
int ans = 0;
for (int i = 0; i < wordsSize-1; i++) {
uint32_t iNum = to_bin(words[i]);
size_t iLen = strlen(words[i]);
for (int j = i+1; j < wordsSize; j++) {
int product = strlen(words[j]) * iLen;
if (product < ans) continue;
if (to_bin(words[j]) & iNum) continue;
ans = MAX(ans, product);
}
}
return ans;
}