我想玩猜字謎 leetcode算法題每日一練- 猜字謎

由雕龍文庫 分享時間：2024-02-22 05:55:45 收藏本文

算法題每日一練- 猜字謎

題目

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

字謎的迷面按字符串形式給出我想玩猜字謎，如果一個單詞 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; }