Leetcode 318. Maximum Product of Word Length

我雖然反對在軟體工程師面試時考白板題,不過對於 Leetcode 的態度就沒這麼反對。

偶爾會解一下 Leetcode Daily 作為工作前的醒腦準備,也不失為一種生活樂趣。

題目

318. Maximum Product of Word Lengths

從範例中不難看出,本題需要的工作有兩個:

  • 找出兩個使用不重複字母的字串
  • 上述兩個字串的長度之乘積
  • 找出乘積的最大值,即為解答

解題思路

本題最核心的問題應該是:如何驗證兩個字串是否使用了相同的字元。

假設當前存在兩個字串 abcdef,我們嘗試將其轉變為以下形式:

a b c d e f
1 1 1 0 0 0 (abc) = 56
0 0 0 1 1 1 (def) = 7

根據使用的字元,將其安排一個 bit 做記錄,這麼一來便可以得到兩個整數(abc = 56def = 7),只要將這兩個值做一次 & 如果為 0 表示使用的字元沒有重複。

如此一來,整個實作如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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(),這不利於效能。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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] 仍會被重複計算)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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),但很顯然地可以再進一步壓榨

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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() 的時候如果可以順便回傳字串的長度,對於一些極端的案例(例如超長字串)就可以起到加速的效果。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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 裡面。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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

1
2
3
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 操作),感覺就可以水一篇文(?