[LeetCode] - Most Common Word

 

문자열 변수 paragraph와 문자열 배열 banned가 주어진다.

paragraph에서 banned에 포함되지 않는 가장 자주 나오는 문자를 반환하시오.

답은 고유하며 한 단어를 보장한다.

paragraph의 단어들은 대소문자의 구분하지 않으며 답은 소문자로 반환하시오.

 

/* 
생각해보자. paragraph는 space를 기준으로 단어를 나눈다. 
그렇다면 일단 단어를 공백을 기준으로 나눠 단어의 배열을 만들자. 
거기서 banned에 포함된 단어를 삭제 남은 단어들 중에서 
가장 빈번하게 나오는 단어를 소문자로 리턴 
1. 소문자로 
2. 단어를 공백 기준으로 나눠 단어 배열만들기 
3. banned 단어 제외시키기 
4. 가장 빈번한 단어 고르기 
5. 리턴 */
class Solution {
    public String mostCommonWord(String paragraph, String[] banned) {

        paragraph = paragraph.toLowerCase();
        System.out.println(paragraph);
        String match = "[^\uAC00-\uD7A3xfe0-9a-zA-Z\\s]";
        paragraph = paragraph.replaceAll(match, " ");
        paragraph = paragraph.replaceAll(" ", " ");
        System.out.println(paragraph);
        String[] words = paragraph.split(" ");
        ArrayList<String> wordsList = new ArrayList<>(Arrays.asList(words));
        ArrayList<String> bannedList = new ArrayList<>(Arrays.asList(banned));
        Map<String, Integer> map = new HashMap<>();
        wordsList.removeAll(bannedList);
        for (int idx = 0; idx < wordsList.size(); idx++) {
            System.out.println(wordsList.get(idx));
            map.put(wordsList.get(idx), map.getOrDefault(wordsList.get(idx), 0) + 1);
        }
        return Collections.max(map.entrySet(), Map.Entry.comparingByValue()).getKey();
    }
}
Runtime: 28 ms Memory Usage: 39.8 MB 풀긴 했지만 끔찍하다. 빨리 개선해야겠다.

 

Solution 1

String Processing in Pipeline

class Solution {
    public String mostCommonWord(String paragraph, String[] banned) {

        // 1). replace the punctuations with spaces,
        // and put all letters in lower case
        String normalizedStr = paragraph.replaceAll("[^a-zA-Z0-9 ]", " ").toLowerCase();

        // 2). split the string into words
        String[] words = normalizedStr.split("\\s+");

        Set<String> bannedWords = new HashSet();
        for (String word : banned)
            bannedWords.add(word);

        Map<String, Integer> wordCount = new HashMap();
        // 3). count the appearance of each word, excluding the banned words
        for (String word : words) {
            if (!bannedWords.contains(word))
                wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
        }

        // 4). return the word with the highest frequency
        return Collections.max(wordCount.entrySet(), Map.Entry.comparingByValue()).getKey();
    }
}

 

Solution 2 Character Processing in One-Pass

class Solution {
    public String mostCommonWord(String paragraph, String[] banned) {

        Set<String> bannedWords = new HashSet();
        for (String word : banned)
            bannedWords.add(word);

        String ans = "";
        int maxCount = 0;
        Map<String, Integer> wordCount = new HashMap();
        StringBuilder wordBuffer = new StringBuilder();
        char[] chars = paragraph.toCharArray();

        for (int p = 0; p < chars.length; ++p) {
            char currChar = chars[p];

            // 1). consume the characters in a word
            if (Character.isLetter(currChar)) {
                wordBuffer.append(Character.toLowerCase(currChar));
                if (p != chars.length - 1)
                    // skip the rest of the processing
                    continue;
            }

            // 2). at the end of one word or at the end of paragraph
            if (wordBuffer.length() > 0) {
                String word = wordBuffer.toString();
                // identify the maximum count while updating the wordCount table.
                if (!bannedWords.contains(word)) {
                    int newCount = wordCount.getOrDefault(word, 0) + 1;
                    wordCount.put(word, newCount);
                    if (newCount > maxCount) {
                        ans = word;
                        maxCount = newCount;
                    }
                }
                // reset the buffer for the next word
                wordBuffer = new StringBuilder();
            }
        }
        return ans;
    }
}