LeetCode 819. Most Common Word(StringBuilder 이용)

 

 

 

Problem:

•  Given a string paragraph and a string array of the banned words banned, return the most frequent word that is not banned. It is guaranteed there is at least one word that is not banned, and that the answer is unique.

 

Constraints:

• 1 <= paragraph.length <= 1000
• paragraph consists of English letters, space ' ', or one of the symbols: "!?',;."
• 0 <= banned.length <= 100
• 1 <= banned[i].length <= 10
• banned[i] consists of only lowercase English letters.

 

class Solution {
    Set<String> bannedSet = new HashSet<>();
    Map<String, Integer> count = new HashMap<>();
    int max;
    String res;
    
    public String mostCommonWord(String paragraph, String[] banned) {
        StringBuilder sb = new StringBuilder("");
        for(String s : banned)  bannedSet.add(s);
        
        for(char c : paragraph.toCharArray()){
            if(c>='a'&&c<='z')  // replaceAll(정규 표현식, " ")으로 푸는 방법보다 빠르다. 
                sb.append(c);
            else if(c>='A'&&c<='Z')  
                sb.append((char)(c+'a'-'A'));
            else    
                process(sb);
        }
        
        process(sb);   // ex) paragraph="Bob" -> 마지막 단어가 process() 안되기 때문에 for문 나와서 한 번 더 해줘야한다.
        
        return res;
    }
    
    public void process(StringBuilder sb){
        if(sb.length()>0){
            String cur = sb.toString();
            if(!bannedSet.contains(cur)){
                int key = count.getOrDefault(cur,0)+1;
                count.put(cur, key);
                if(key > max){
                    max=key;
                    res=cur;
                }
            }   
        }
        sb.setLength(0);
    }
}

• String str ="" , str += "a" 보다 StringBuilder sb = new StringBuilder(""), sb.append("a")가 더 빠르다. 
• 정규 표현식( replaceAll("[!?',;.]" , " "))을 이용해서 풀었을 때 그 후에 또 replaceAll(" " , "")을 해줘야해서 비효율적이었다. 
  
• process 메소드에서 처음엔

  String cur = sb.toString();
  if(!bannedSet.contains(cur)&&cur.length()>0){
  	...
  }​

        => 이렇게 해뒀는데 sb.legnth()>0로 먼저 거른뒤에 하는 게 더 빠르다.

 

Reference:

• https://leetcode.com/problems/most-common-word/discuss/1087237/Java-100-Faster-2ms