我的問題類似于How can i use haskell to check if a list contains the values in a tuple，但在我的情況下，具有必須全部在我的原始串列中的值的串列是字母表。有 26 個對 的呼叫elem，所有的 AND 連接在一起，感覺真的很混亂。
有沒有更簡潔的方法來檢查給定串列是否包含另一個串列中的所有元素，其中另一個串列有 26 個專案長？
uj5u.com熱心網友回復：
我喜歡 user1984 的答案，但它確實讓您處理非字母字符的方式有些隱含。這是一個幾乎同樣簡單的方法，但不需要額外的代碼來處理非字母字符。基本思想是往另一個方向走；他們的答案建立了一個集合，這個一個通過一次洗掉一個字符來撕裂一個。它也是 O(n)，就像他們的一樣。
import qualified Data.Set as S
isPangram :: String -> Bool
isPangram = S.null . foldr S.delete (S.fromList ['a'..'z'])
如果您想要不區分大小寫，您可以匯入Data.Char并更改S.delete為(S.delete . toLower).
uj5u.com熱心網友回復：
我的理解是，您正在嘗試檢查字串是否為全字組詞，這意味著它包含所有 [插入您的首選語言] 字母表。
以下代碼使用Data.Set. 根據定義，集合資料結構不能包含重復元素。在將字串中的所有字符添加到集合后，我們使用集合的這個屬性來計算其中的元素數量。如果它等于我們正在處理的字母表的數量，則表示該字串包含了該字母表的所有字符，因此它是一個 pangram。
請注意，此代碼不考慮大小寫字母之間的差異，也計算空格和標點符號。如果有任何這些情況，這會給你錯誤的答案。通過一些調整，你可以讓它作業。
正如 Daniel Wagner 指出的那樣，該解決方案的時間復雜度n * log 26僅n在 Big O 中。原因是雖然 Haskell 的默認集合是平衡樹，但集合中的元素數量永遠不會超過 26，所以它變成了線性。使用集合的散列實作可能會導致對非常大的字串進行一些優化。空間復雜度是恒定的，因為我們使用的額外空間永遠不會超過 26 個字符。
import qualified Data.Set as S
isPangram :: [Char] -> Bool
isPangram s = length (S.fromList s) == 26
uj5u.com熱心網友回復：
這是基于丹尼爾瓦格納的回答，但如果找到所有字母，它會提前完成，而他會遍歷整個串列，然后向后洗掉元素，然后在回到開頭時給出答案。
import qualified Data.Set as S
import Data.Set (Set)
letters :: Set Char
letters = S.fromList ['a'..'z']
isPangram :: String -> Bool
isPangram xs0 = go xs0 letters
where
go :: String -> Set Char -> Bool
go [] letters = S.null letters
go (c : cs) letters =
S.null letters || go cs (S.delete c letters)
您可能想知道為什么我首先匹配字串并letters在匹配項下檢查，而不是相反。好吧，那只是因為使用foldr以下內容重寫它很有趣：
isPangram :: String -> Bool
isPangram xs0 = foldr step S.null xs0 letters
where
step :: String -> Set Char -> Bool
step c r letters =
S.null letters || r (S.delete c letters)
對于字母表之類的東西，Data.Set實際上并不是最有效的方式。最好使用類似 的東西IntSet，它更緊湊且速度更快。
import qualified Data.IntSet as S
import Data.IntSet (IntSet)
letters :: IntSet
letters = S.fromList (map fromEnum ['a'..'z'])
isPangram :: String -> Bool
isPangram xs0 = foldr step S.null xs0 letters
where
step :: String -> IntSet -> Bool
step c r letters =
S.null letters || r (S.delete (fromEnum c) letters)
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/330329.html