程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> leetcode筆記之Maximum Product of Word Lengths

leetcode筆記之Maximum Product of Word Lengths

編輯:關於C++

一. 題目描述

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:
Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16
The two words can be "abcw", "xtfn".

Example 2:
Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return 4
The two words can be "ab", "cd".

Example 3:
Given ["a", "aa", "aaa", "aaaa"]
Return 0
No such pair of words.

二. 題目分析

題目大意:給定一個字符串數組words,尋找length(words[i]) * length(words[j])的最大值,其中words[i]words[j] 兩個單詞不包含相同的字母。你可以假設每一個單詞只包含小寫字母。如果不存在這樣的兩個單詞,結果返回0。

對於題目的要求,首先需要統計words中每個單詞的小寫字母a-z是否存在,然後一次枚舉words[i]words[j],找出最大長度maxLength

這裡可以使用32位整數來表示每個單詞的字母存在情況。我們知道小寫字母a~z有26位,因此一個32位整數的低26位可以用於標記a~z各個字母是否出現,比如最低位標記'a'是否出現;第二位標記'b'是否出現…以此類推,以下給出兩個例子:

對於abcd,可被標記為:0000 0000 0000 0000 0000 0000 0000 1111

對於acxy,可被標記為:0000 0001 1000 0000 0000 0000 0000 0101

因此,只需申請一個int srtToBit[26]的數組,通過簡單的位操作即可完成字符串標記。

標記完成後,開始兩兩比較數組,如"abcd"被標記為:0000 0000 0000 0000 0000 0000 0000 1111"wxyz"被標記為:1111 0000 0000 0000 0000 0000 0000 0000,由於兩字符串不含相同的字母,因此兩個整數值相與(&),結果必然為0,這樣,就找出了這樣的字符串對。

三. 示例代碼

class Solution {
public:
    int maxProduct(vector& words) {
        int SIZE = words.size();
        vector strToBit(SIZE);
        // 將各字符串轉換為32位整數,用各位上的狀態
        // 0 & 1 來表示是否出現對應的字母,如acxyz為
        // 1010 0000 0000 0000 0000 0000 0000 0111
        // 32為整數存放在數組strToBit中
        for (int i = 0; i < SIZE; ++i)
        {
            int temp = 0;
            for (int j = 0; j < words[i].size(); ++j)
            {
                temp |= (1 << ('x' - words[i][j]));

            }
            strToBit[i] = temp;
        }
        int maxLength = 0;
        // 分別對各字符串進行與運算
        for (int i = 0; i < SIZE - 1; ++i)
            for (int j = i + 1; j < SIZE; ++j)
                if ((strToBit[i] & strToBit[j]) == 0)
                    maxLength = max(maxLength, static_cast(words[i].size() * words[j].size()));

        return maxLength;
    }
};

四. 小結

實現該題目的方法有很多,使用位運算是比較高效和精妙的方法。

   
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved