1、題目信息

• https://leetcode.cn/problems/aseY1I/description/

給定一個字符串數組 words，請計算當兩個字符串 words[i] 和 words[j] 不包含相同字符時，它們長度的乘積的最大值。假設字符串中只包含英語的小寫字母。如果沒有不包含相同字符的一對字符串，返回 0。示例 1：
輸入：words = ["abcw","baz","foo","bar","fxyz","abcdef"]
輸出：16 
解釋：這兩個單詞為 "abcw", "fxyz"。它們不包含相同字符，且長度的乘積最大。示例 2：
輸入：words = ["a","ab","abc","d","cd","bcd","abcd"]
輸出：4 
解釋：這兩個單詞為 "ab", "cd"。示例 3：
輸入：words = ["a","aa","aaa","aaaa"]
輸出：0 
解釋：不存在這樣的兩個單詞。

2、審題

• 輸入一個字符串數組，數組兩個元素中的字符串，可能存在相同的字符，要求尋找沒有相同字符的兩個字符串，要求他們的長度乘積最大并返回
• 如果任意兩個字符串都存在相同的字符，結果返回0

3、解法1：暴力解法

思路：

• 解題關鍵在于：尋找出兩個字符串，他們之間不存在相同的字符
  • 四層for循環，外雙層for循環，從字符串數組中尋找兩個不同的字符串，內層for循環判斷兩個字符串兩兩是否存在相同的字符
  • 如果存在相同字符，退出內部兩層for循環，從新尋找其他字符串組合
  • 如果不存在相同字符，求出兩個字符串的最大乘積
• 暴力解法會超出時間限制

代碼實現：

int maxProduct1(vector<string> &words)
{int res = 0;int size = words.size();for (int i = 0; i < size; i++){for (int j = i + 1; j < size; j++){std::string str1 = words[i];std::string str2 = words[j];int len1 = str1.length();int len2 = str2.length();int h = 0;for (; h < len1; h++){// 遍歷str1字符串中的字符，判斷該字符在str1中是否存在，存在則退出當前for循環bool find = false;for (int g = 0; g < len2; g++){if (str1[h] == str2[g]){find = true;break;}}if (find){break;}}if (h == len1) // h遍歷到str1字符串末尾，說明不存在相同字符{int productLen = len1 * len2;res = std::max(res, productLen);}}}return res;
}

4、解法2：哈希表解法

思路：

• 暴力解法中有四層for循環，其中外層兩個for循環是尋找兩個需要比較的字符串，內層兩個for循環是判斷兩個字符串是否有相同的字符
• 內層for循環可簡化，通過哈希表的方式記錄每個字符串中，單個字符是否出現過
  • 哈希表使用二維數組結構，一維數組元素存儲的是數組中的單個字符串，一維數組長度是字符串數組長度，
  • 二維數組內層存儲的是單個字符串是否出現-使用bool表示，因為字符串由小寫字母組成，所以二維數組的長度是26

代碼實現：

int maxProduct2(vector<string> &words)
{int res = 0;int size = words.size();vector<vector<bool>> arr(size, vector<bool>(26, false));// 遍歷單個字符串，判斷單個字符出現的位置，在出現的位置上設置arr數組元素為bool值for (int i = 0; i < size; i++){std::string str = words[i];for (int j = 0; j < str.length(); j++){arr[i][str[j] - 'a'] = true;}}// 字符串兩兩判斷是否存在相同字符for (int i = 0; i < size; i++){for (int j = i + 1; j < size; j++){std::string str1 = words[i];std::string str2 = words[j];int len1 = str1.length();int len2 = str2.length();int h = 0;for (; h < len1; h++){int chIndex = str1[h] - 'a'; // 是第幾個字符if (arr[i][chIndex] && arr[j][chIndex]){break;}}if (h == len1){// 沒有相同的字符int productLen = len1 * len2;res = std::max(res, productLen);}}}return res;
}

優化：

• 第三層for循環改為遍歷26個字符，判斷兩個字符是否存在相同的字符

int maxProduct3(vector<string> &words)
{int res = 0;int size = words.size();vector<vector<bool>> arr(size, vector<bool>(26, false));// 遍歷單個字符串，判斷單個字符出現的位置，在出現的位置上設置arr數組元素為bool值for (int i = 0; i < size; i++){std::string str = words[i];for (int j = 0; j < str.length(); j++){arr[i][str[j] - 'a'] = true;}}// 字符串兩兩判斷是否存在相同字符for (int i = 0; i < size; i++){for (int j = i + 1; j < size; j++){int h = 0;for (; h < 26; h++){if (arr[i][h] && arr[j][h]){break;}}if (h == 26){// 沒有相同的字符int productLen = words[i].length() * words[j].length();res = std::max(res, productLen);}}}return res;
}

5、解法3：位運算

思路：

• 之前26個字母位置存在的是bool類型，表示字符串包含的字母在26個字母位置是否存在
• bool類型只有true和false，也可以替換為使用int類型，該字母存在值為1，否則為0
  那最后如何判斷兩個字符中是否存在相同的字母呢？
• 使用一維整數數組，一個int整數類型長度為32字節，可以滿足26個的標識
• 遍歷所有的字符串數組，再遍歷單個字符串，獲取到字符，往左移該字符在26個字母中的位置，并且標記為1
• 最后兩個整數進行&與運算，其結果為1，說明存在相同字母

將字符串中包含的字母標記，使用int類型進行表示，轉換成二進制方式

i:0 ,word:abcw ,arr item:4194311
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1
i:1 ,word:baz ,arr item:33554435
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
i:2 ,word:foo ,arr item:16416
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0
i:3 ,word:bar ,arr item:131075
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
i:4 ,word:fxyz ,arr item:58720288
0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
i:5 ,word:abcdef ,arr item:63
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1

代碼實現：

int maxProduct(vector<string> &words)
{int res = 0;int size = words.size();vector<int> arr(size, 0);for (int i = 0; i < size; i++){std::string str = words[i];for (int j = 0; j < str.length(); j++){arr[i] |= (1 << (str[j] - 'a'));}}// 字符串兩兩判斷是否存在相同字符for (int i = 0; i < size; i++){for (int j = i + 1; j < size; j++){if ((arr[i] & arr[j]) == 0){// 沒有相同的字符int productLen = words[i].length() * words[j].length();res = std::max(res, productLen);}}}return res;
}

6、總結

• 輸入的是一個字符串數組，要從中選出兩個不同的字符串元素，需要通過兩層for循環去查找
• 而要判斷兩個字符串中是否存在相同的字符，則需要對兩個字符串分別進行遍歷，判斷是否存在相同的字符
• 采用空間換時間的方式，先對字符串進行標記處理，判斷當前字符串在26個字母數組中，存在幾個字母。
• 通過位運算和移位的方式，不斷獲取到字符串中的字符，并進行標記到數組中。