算法題每日一練- 猜字謎

題目

外國(guó)友人仿照中國(guó)字謎設(shè)計(jì)了一個(gè)英文版猜字謎小游戲，請(qǐng)你來(lái)猜猜看吧。

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

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

返回一個(gè)答案數(shù)組 ，數(shù)組中的每個(gè)元素 [i] 是在給出的單詞列表 中可以作為字謎迷面 [i] 所對(duì)應(yīng)的謎底的單詞數(shù)目。

示例：

輸入：words = ["aaaa","asas","able","ability","actt","actor","access"], puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]輸出：[1,1,3,2,4,0]解釋?zhuān)?span id="wayaqiu" class="token number">1 個(gè)單詞可以作為 "aboveyz" 的謎底 : "aaaa" 1 個(gè)單詞可以作為 "abrodyz" 的謎底 : "aaaa"3 個(gè)單詞可以作為 "abslute" 的謎底 : "aaaa", "asas", "able"2 個(gè)單詞可以作為 "absoryz" 的謎底 : "aaaa", "asas"4 個(gè)單詞可以作為 "actresz" 的謎底 : "aaaa", "asas", "actt", "access"沒(méi)有單詞可以作為 "gaswxyz" 的謎底，因?yàn)榱斜碇械膯卧~都不含字母 'g'。

提示：

分析

實(shí)現(xiàn)這題的思路其實(shí)很簡(jiǎn)單：

首先，根據(jù)題意得符合謎底的必要條件： 必須由謎面中的字符組成，即一個(gè)謎底word中的字符一定都來(lái)源于一個(gè)謎面。謎底必須包含謎面中的第一個(gè)字符。 明白了兩個(gè)必要條件，所以思路就出來(lái)了，遍歷所有謎面，將謎底逐個(gè)代入進(jìn)去驗(yàn)證是否滿(mǎn)足條件。 實(shí)現(xiàn)

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; // 遍歷數(shù)組 for (String word : words) { // 第一個(gè)條件，謎底必須包含謎面puzzle中的第一個(gè)字符 if (word.contains(Character.toString(puzzle.charAt(0)))) { for (int k = 0; k < word.length(); k++) { char c = word.charAt(k); // 第二個(gè)條件，謎底的字符全部來(lái)源于謎面的字符 if (!puzzle.contains(Character.toString(c))) { flag = false; break; } flag = true; } if (flag){ count++; } } } result.add(count); } return result; }

總結(jié)

時(shí)間復(fù)雜度為O(MNV),即謎底的長(zhǎng)度謎面word的長(zhǎng)度單個(gè)字符串的長(zhǎng)度，空間復(fù)雜度為O(N),即對(duì)應(yīng)謎底的結(jié)果集合。當(dāng)然，本題是存在優(yōu)化點(diǎn)的，就是使用的思想，減少一層遍歷，讀者可以查看官方題解-猜字謎

免責(zé)聲明：本文系轉(zhuǎn)載，版權(quán)歸原作者所有；旨在傳遞信息，不代表本站的觀點(diǎn)和立場(chǎng)和對(duì)其真實(shí)性負(fù)責(zé)。如需轉(zhuǎn)載，請(qǐng)聯(lián)系原作者。如果來(lái)源標(biāo)注有誤或侵犯了您的合法權(quán)益或者其他問(wèn)題不想在本站發(fā)布，來(lái)信即刪。