Leetcode 318. Maximum Product of Word Length

我雖然反對在軟體工程師面試時考白板題，不過對於 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;
}

重複計算的 words binary

雖然上一次的優化減少了 words[i] 的 binary 計算，但仍然是不足的（因為 words[j] 仍會被重複計算）

int maxProduct(char ** words, int wordsSize) {
    int ans = 0;

    uint32_t bin[wordsSize];

    for (int i = 0; i < wordsSize; i++)
        bin[i] = to_bin(words[i]);
    
    for (int i = 0; i < wordsSize-1; i++) {
        for (int j = i+1; j < wordsSize; j++) {
            if (bin[i] & bin[j]) continue;
            ans = MAX(ans, strlen(words[i]) * strlen(words[j]));
        }
    }

    return ans;
}

重複計算的 strlen()

即便上述的兩次優化已經可以取得很明顯的進步（679ms -> 38ms），但很顯然地可以再進一步壓榨

int maxProduct(char ** words, int wordsSize) {
    int ans = 0;

    uint32_t bin[wordsSize], len[wordsSize];
    for (int i = 0; i < wordsSize; i++) {
        bin[i] = to_bin(words[i]);
        len[i] = strlen(words[i]);
    }

    for (int i = 0; i < wordsSize-1; i++) {
        for (int j = i+1; j < wordsSize; j++) {
            if (bin[i] & bin[j]) continue;
            ans = MAX(ans, len[i] * len[j]);
        }
    }
}

字串的重複疊代

我們知道，在 C 語言中的字串是以 NULL byte 結尾，這表示在計算 to_bin() 跟 strlen() 的時候都會重複去針對每一個字元去疊代，直到找到 \0 為止。

註：事實上，strlen() 在大多數的實現中不會每個字元去疊代直到找到 \0 為止，通常會用一些 bit 操作搭配 CPU 指令去優化。

如此一來，在使用 to_bin() 的時候如果可以順便回傳字串的長度，對於一些極端的案例（例如超長字串）就可以起到加速的效果。

uint32_t to_bin(char *str, int *len) {
    int ret = 0;
    for (*len = 0; *str; str++, (*len)++) // 注意：要用 (*len)++ 而不是 *len++
        ret |= 1 << *str - 'a';
    return ret;
}

int maxProduct(char ** words, int wordsSize) {
    int ans = 0;

    uint32_t bin[wordsSize], len[wordsSize];
    for (int i = 0; i < wordsSize; i++) {
        int sz;
        bin[i] = to_bin(words[i], &sz);
        len[i] = sz;
    }

    for (int i = 0; i < wordsSize-1; i++) {
        for (j = i+1; j < wordsSize; j++) {
            if (bin[i] & bin[j]) continue;
            ans = MAX(ans, len[i] * len[j]);
        }
    }

    return ans;
}

針對題目限制再擠一點點效能

已知題目限制：

• 2 <= words.length <= 1000
• 1 <= words[i].length <= 1000
• words[i] 僅有小寫的英文字母

因為每個 word 長度 <= 1000，所以將 uint32_t len[wordsSize] 轉為 uint16_t len[wordsSize] 即可節省一半的字串長度儲存空間。

註：如果 word 長度可以 < 64，那甚至可以把這個資料塞進 bin 裡面。

uint32_t to_bin(char *str) {
    int ret = 0;
    int len = 0;
    for (*len = 0; *str; str++, len++)
        ret |= 1 << *str - 'a';
    ret = len << 26 | ret;
    return ret;
}

uint32_t n = to_bin("abc")
// bin = n & 0x3FFFFF
// len = n >> 26

剩下的就交給 compiler

inline uint32_t to_bin(const char *str, int *len) {
    // more
}

• 利用 inline 讓編譯器決定如何優化 to_bin()
• 將 char *str 改為 const char *str 指示編譯器 str 並不會被改變

結論

事實上，會特別寫一篇文章說這題主要是因為它足夠有趣：把 string 轉成 integer 的方法再去用 & 跟其它字串值做比對。

再加上寫這題時用上的一大堆優化策略（其實應該還有一些優化手段，例如在 to_bin 中用更多的 bit 操作），感覺就可以水一篇文（？