算法題每日一練- 猜字謎

題目

外國友人仿照中國字謎設計了一個英文版猜字謎小游戲，請你來猜猜看吧。

字謎的迷面 按字符串形式給出我想玩猜字謎，如果一個單詞 word 符合下面兩個條件，那么它就可以算作謎底：

例如我想玩猜字謎，如果字謎的謎面是 “”我想玩猜字謎，那么可以作為謎底的單詞有 “”, “”, 和 “”；而 “”（不含字母 “a”）以及 “”（其中的 “s” 沒有出現在謎面中）都不能作為謎底。

返回一個答案數組 ，數組中的每個元素 [i] 是在給出的單詞列表 中可以作為字謎迷面 [i] 所對應的謎底的單詞數目。

示例：

輸入：words = ["aaaa","asas","able","ability","actt","actor","access"], puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]輸出：[1,1,3,2,4,0]解釋：1 個單詞可以作為 "aboveyz" 的謎底 : "aaaa" 1 個單詞可以作為 "abrodyz" 的謎底 : "aaaa"3 個單詞可以作為 "abslute" 的謎底 : "aaaa", "asas", "able"2 個單詞可以作為 "absoryz" 的謎底 : "aaaa", "asas"4 個單詞可以作為 "actresz" 的謎底 : "aaaa", "asas", "actt", "access"沒有單詞可以作為 "gaswxyz" 的謎底，因為列表中的單詞都不含字母 'g'。

提示：

分析

實現這題的思路其實很簡單：

首先，根據題意得符合謎底的必要條件： 必須由謎面中的字符組成，即一個謎底word中的字符一定都來源于一個謎面。謎底必須包含謎面中的第一個字符。 明白了兩個必要條件，所以思路就出來了，遍歷所有謎面，將謎底逐個代入進去驗證是否滿足條件。 實現

public static List<Integer> findNumOfValidWords(String[] words, String[] puzzles) { List<Integer> result = new ArrayList<>(); int count; boolean flag = false; // 遍歷謎面 for (String puzzle : puzzles) { count = 0; // 遍歷數組 for (String word : words) { // 第一個條件，謎底必須包含謎面puzzle中的第一個字符 if (word.contains(Character.toString(puzzle.charAt(0)))) { for (int k = 0; k < word.length(); k++) { char c = word.charAt(k); // 第二個條件，謎底的字符全部來源于謎面的字符 if (!puzzle.contains(Character.toString(c))) { flag = false; break; } flag = true; } if (flag){ count++; } } } result.add(count); } return result; }

總結

時間復雜度為O(MNV),即謎底的長度謎面word的長度單個字符串的長度，空間復雜度為O(N),即對應謎底的結果集合。當然，本題是存在優化點的，就是使用的思想，減少一層遍歷，讀者可以查看官方題解-猜字謎

免責聲明：本文系轉載，版權歸原作者所有；旨在傳遞信息，不代表本站的觀點和立場和對其真實性負責。如需轉載，請聯系原作者。如果來源標注有誤或侵犯了您的合法權益或者其他問題不想在本站發布，來信即刪。