2018-10-26 00:32:05

問題描述：

問題求解：

方法一、Trie

最長出現(xiàn)的字符串，最容易想到的解法就是Trie樹了，于是首先使用Trie樹進(jìn)行了實(shí)現(xiàn)，代碼量有點(diǎn)大，當(dāng)然了是可以A掉的，只是對于這種Easy的題，理論上是不該超過50行代碼的。

public class MostCommonWord {class TrieNode {public TrieNode[] next = new TrieNode[26];public int cnt = 0;public String word = null;}public String mostCommonWord(String paragraph, String[] banned) {int[] maxCnt = new int[1];String[] res = new String[1];TrieNode root = buildTrie(paragraph, banned);helper(root, maxCnt, res);return res[0];}private void helper(TrieNode root, int[] maxCnt, String[] res) {if (root.cnt > maxCnt[0]) {maxCnt[0] = root.cnt;res[0] = root.word;}for (int i = 0; i < 26; i++) {if (root.next[i] != null) helper(root.next[i], maxCnt, res);}}private TrieNode buildTrie(String s, String[] banned) {Set<Character> set = new HashSet<>();Set<String> b = new HashSet<>();for (String i : banned) b.add(i);set.add(' ');set.add('!');set.add('?');set.add('\'');set.add(',');set.add(';');set.add('.');TrieNode root = new TrieNode();String lowS = s.toLowerCase() + ' ';char[] chs= lowS.toCharArray();for (int i = 0; i < chs.length; i++) {while (i < chs.length && set.contains(chs[i])) i++;TrieNode cur = root;for (int j = i; j < chs.length; j++) {if (set.contains(chs[j])) {cur.word = lowS.substring(i, j);if (!b.contains(cur.word)) cur.cnt++;i = j;break;}if (cur.next[chs[j] - 'a'] == null) cur.next[chs[j] - 'a'] = new TrieNode();cur = cur.next[chs[j] - 'a'];}}return root;}public static void main(String[] args) {System.out.println('\'');} }

方法二、split

作為一條Easy必然是有簡單解，但是還是有點(diǎn)tricky的，這里使用了正則的replaceAll函數(shù)來將其他字符轉(zhuǎn)成” “，之后再split并統(tǒng)計(jì)即可。

public String mostCommonWord(String paragraph, String[] banned) {String[] strs = paragraph.replaceAll("[!?',;.]", " ").toLowerCase().split(" ");Map<String, Integer> map = new HashMap<>();Set<String> set = new HashSet<>();for (String i : banned) set.add(i);set.add("");for (String s : strs) {if (!set.contains(s)) {int cnt = map.getOrDefault(s, 0);map.put(s, ++cnt);}}int maxCnt = 0;String res = "";for (String s : map.keySet()) {if (map.get(s) > maxCnt) {maxCnt = map.get(s);res = s;}}return res;}

?

轉(zhuǎn)載于:https://www.cnblogs.com/TIMHY/p/9853778.html

總結(jié)

以上是生活随笔為你收集整理的最常出现的字符串 Most Common Word的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。