884. 兩句話中的不常見單詞

2023-03-28 09:08 作者:目標(biāo)力扣Knight 0人讀過 | 我要投稿

方法一：字符串切割 + 哈希

純模擬的思路，先將字符串切割為單詞，然后將單詞存入哈希表中，逐個遍歷哈希表，同時判斷鍵在另外一個哈希表的存儲情況，不再則存入作為返回值的數(shù)組當(dāng)中；

C++版本

復(fù)雜度分析

時間復(fù)雜度: O(C)。此題沒有明確給出單詞的個數(shù)，我們將字符數(shù)組轉(zhuǎn)換為單詞數(shù)組的時候，復(fù)雜度為O(N)，此處n 指的是字符串 s1 / s2的長度，轉(zhuǎn)換后的單詞的個數(shù)不確定，通?？紤]極端情況，若每間隔一位制造一個空格，那么復(fù)雜度約為33，一個字母只能算作字母，最少需要兩個，小于極限情況：由26個字母抽取兩個組成單詞且去重的個數(shù)—>26 * 25 / 2 = 325; 假設(shè)每個單詞都出現(xiàn)一次，那么總的復(fù)雜度為 200 + (33 + 33) * 2 = 332,因此在較小的數(shù)據(jù)集中當(dāng)作常數(shù)C；
空間復(fù)雜度：O(C)。理由如上，一般遍歷次數(shù)就是空間的單位長度個數(shù)；

在A哈希表而不再B哈希表等價于，在兩個哈希表的合集中之出現(xiàn)一次，因此可以用一個哈希表來存儲兩個字符串的單詞，最后返回僅在哈希表出現(xiàn)一次的單詞即可；

C++版本

復(fù)雜度分析

時間復(fù)雜度：O(N)。對于原字符數(shù)組轉(zhuǎn)換為單詞，復(fù)雜度不變，而對來自于兩個字符數(shù)組構(gòu)成的哈希表，由于其最大組合為325，而在假設(shè)兩個字符數(shù)組提取長度為2，間隔一位取空格，最終得到的單詞個數(shù)為33 * 2，仍然小于325的最大組合個數(shù)，其次作為返回值，極限情況可以每個單詞都只出現(xiàn)一次，且兩個哈希表中的單詞均只出現(xiàn)一次且唯一，那么復(fù)雜度為 200 + 33 * 2 + 33 * 2=332。
空間復(fù)雜度: O(N)。理由同上；

此次在使用C++求字符串切割后的單詞，首次使用了 stringstream語法，對我來說新知識，而且顯而易見，官方題解的作者進一步做了封裝，因兩個字符串均需要提取單詞；
而在手動實現(xiàn)將字符串轉(zhuǎn)換為單詞數(shù)組的過程中，很容易因為雙指針的偏移方式導(dǎo)致錯誤，比如我出錯的原因就是沒有分清單個字母存入單詞串的方法，究竟存儲字母和指針偏移那個在前，這會導(dǎo)致關(guān)聯(lián)問題，起始字母是否作為雙指針的第二指針先行插入，這以上兩個問題導(dǎo)致了長達30分鐘的debug，需要特別注意，但兩種循環(huán)嵌套剝離單詞的模型是固定的，也就是雙指針；

標(biāo)簽：