LeetCode - Search Suggestions System

풀이 방법

가 주어졌다고 가정하자.

  1. Product를 Lexical Order로 정렬한다 => [“monitor”, “mousepad”]
  2. Product를 순회하며 아래 로직을 수행한다.
    • 선택된 Product의 [0, 0] ~ [0, length - 1] 까지 순회하며 아래 로직을 수행한다.
      • [0, 0] => “m”이며, 이를 Map에 추가한다 => Map(“m” => [“monitor”])
      • [0, 1] => “mo”이며, 이를 Map에 추가한다 => Map(“m” => [“monitor”], “mo” => [“monitor”])
      • [0, 6] => “monitor”이며, 이를 Map에 추가한다 => Map(“m” => [“monitor”], “mo” => [“monitor”], “mon” => [“monitor”] …, “monitor” => [“monitor”])
  3. SearchWord의 [0, 0] ~ [0, length - 1] 까지 순회하며 아래 로직을 수행한다.
    • [0, 0] => “m”이며 이에 해당하는 값을 Map에서 찾아 결과 배열에 추가한다 => List(List(“monitor”,”mousepad”))
    • [0, 1] => “mo”이며 이에 해당하는 값을 Map에서 찾아 결과 배열에 추가한다 => List(List(“monitor”,”mousepad”), List(“monitor”, “mousepad”))
    • [0, 2] => “mou”이며 이에 해당하는 값을 Map에서 찾아 결과 배열에 추가한다 => List(List(“monitor”,”mousepad”), List(“monitor”, “mousepad”), List(“mousepad”))
  4. 결과 배열을 반환한다.

코드

class Solution {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        //Products를 Lexical Order로 정렬
        Arrays.sort(products);
        
        //Product의 suffix로 Map을 생성한다.
        Map<String, List<String>> map = new HashMap<>();
        for(int i = 0; i < products.length; i++){
            StringBuilder sb = new StringBuilder();
            for(int j = 0; j < products[i].length(); j++){
                if(j < searchWord.length() && products[i].charAt(j) != searchWord.charAt(j))
                    break;
                sb.append(products[i].charAt(j));
                if(map.containsKey(sb.toString())){
                    List<String> list = map.get(sb.toString());
                    if(list.size() < 3){
                        list.add(products[i]);
                        map.put(sb.toString(), list);
                    }
                }
                else{
                    List<String> list = new ArrayList<>();
                    list.add(products[i]);
                    map.put(sb.toString(), list);
                }
            }
        }
        
        List<List<String>> result = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i <searchWord.length(); i++){
            sb.append(searchWord.charAt(i));
            if(map.containsKey(sb.toString())){
                result.add(map.get(sb.toString()));
            }
            else
                result.add(new ArrayList<>());
        }
        return result;
    }
}