LeetCode算法题-Most Common Word(Java实现)

这是悦乐书的第321次更新,第342篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第190题(顺位题号是819)。给定一个段落和一组禁止词,返回不在禁止词列表中的最常用词。段落中保证至少有一个词没有被禁止,并且答案是独一无二的。禁用单词列表中的单词以小写字母给出,没有标点符号。段落中的单词不区分大小写。答案是小写的。例如:


输入:

paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."

banned = ["hit"]

输出: "ball"

说明:“hit”出现了3次,但这是一个被禁止的词。“ball”出现了两次(没有其他单词),因此它是段落中最常见的非禁止词。请注意,段落中的单词不区分大小写,标点符号被忽略(即使与单词相邻,例如“ball,”),并且“hit”不是答案,即使出现的次数最多,却是一个被禁止的单词。


注意:

  • 1 <= paragraph.length <= 1000.

  • 0 <= banned.length <= 100.

  • 1 <= banned[i].length <= 10.

  • 答案是唯一的,并用小写字母书写(即使它在段落中的出现可能有大写符号,即使它是一个专有名词。)

  • 段落只包含字母,空格或标点符号!?',;.。

  • 没有连字符或带连字符的单词。

  • 单词仅由字母组成,从不包含撇号或其他标点符号。

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 第一种解法

既然题目中说段落字符串会包含标点符号,那么我们先将标点符号替换为空格,并且转为小写,然后遍历禁止单词数组,将段落中出现的禁止单词也替换掉,得到一个新的段落字符串。

因为要计算哪个单词出现的次数最多,所以需要借助HashMap来统计新段落字符串中,每个单词的出现次数。对新段落字符串根据空格拆分,然后存入HashMap中,最后遍历HashMap,找到出现次数最多的字符串单词。

public String mostCommonWord(String paragraph, String[] banned) {
    String str = paragraph.toLowerCase();
    str = str.replace(",", " ");  //!?',;.
    str = str.replace("!", " ");
    str = str.replace("?", " ");
    str = str.replace("'", " ");
    str = str.replace(";", " ");
    str = str.replace(".", " ");
    for (String s : banned) {
        str = str.replaceAll(s, "");
    }
    String[] arr = str.split(" ");
    Map<String, Integer> map = new HashMap<String, Integer>();
    for (String ss : arr) {
        if (!ss.trim().isEmpty()) {
            map.put(ss.trim(), map.getOrDefault(ss.trim(), 0)+1);
        }
    }
    int max = Integer.MIN_VALUE;
    String result = "";
    for (Map.Entry<String,Integer> entry : map.entrySet()) {
        if (entry.getValue() > max) {
            max = entry.getValue();
            result = entry.getKey();
        }
    }
    return result;
}


03 第二种解法

第一步,使用双指针,利用字符串截取的方式,将段落字符串中的每个单词截取出来,存入HashMap。有一点需要注意,如果段落中不包含禁止单词,那么右指针是已经走到了字符串最后一位字符的位置,也需要根据左指针的位置来判断是否要存入HashMap,如果左指针小于右指针,就截取两指针中间的字符串存入HashMap。

第二步,遍历禁止单词数组,从HashMap中移除禁止单词。

第三步,遍历HashMap,找出出现次数最多的单词字符串。

public String mostCommonWord2(String paragraph, String[] banned) {
    if (paragraph.trim().isEmpty()) {
        return "";
    }
    Map<String, Integer> map = new HashMap<String, Integer>();
    int start = 0, end = 0, n = paragraph.length();
    while (end < n) {
        if (Character.isLetter(paragraph.charAt(end))) {
            end++;
        } else {
            if (end > 0 && Character.isLetter(paragraph.charAt(end-1))) {
                String str = paragraph.substring(start, end).toLowerCase();
                start = end;
                map.put(str, map.getOrDefault(str, 0)+1);
            }
            start++;
            end++;
        }
    }
    if (start < end) {
        String str = paragraph.substring(start, end).toLowerCase();
        map.put(str, map.getOrDefault(str, 0)+1);
    }
    for (String s : banned) {
        if (map.containsKey(s)) {
            map.remove(s);
        }
    }
    int max = Integer.MIN_VALUE;
    String result = "";
    for (Map.Entry<String,Integer> entry : map.entrySet()) {
        if (entry.getValue() > max) {
            max = entry.getValue();
            result = entry.getKey();
        }
    }
    return result;
}


04 第三种解法

第一步,利用正则表达式,根据段落字符串中的非字母字符拆分为单词数组,依旧使用HashMap,存入单词和其出现次数。

第二步,遍历禁止单词数组,从HashMap中移除禁止单词。

第三步,遍历HashMap,找出出现次数最多的单词字符串。

public String mostCommonWord3(String paragraph, String[] banned) {
    if (paragraph.trim().isEmpty()) {
        return "";
    }
    String[] arr = paragraph.toLowerCase().split("\\W+");
    Map<String, Integer> map = new HashMap<String, Integer>();
    for (String ss : arr) {
        map.put(ss, map.getOrDefault(ss, 0)+1);
    }
    for (String s : banned) {
        if (map.containsKey(s)) {
            map.remove(s);
        }
    }
    String result = "";
    for (String key : map.keySet()) {
        if (result == "") {
            result = key;
        } else if (map.get(key) > map.get(result)) {
            result = key;
        }
    }
    return result;
}


05 小结

算法专题目前已日更超过五个月,算法题文章190+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

上一篇:model=word2vec.Word2Vec(sentences, size=50) TypeError: __init__() got an unexpected keyword argument


下一篇:分治算法四:二叉堆的创建