[PS] 99클럽 코테 스터디 15일차 TIL (Prefix and Suffix Search)

문제

문제 링크

설명

문자열 배열과 prefix 단어, suffix 단어가 입력으로 주어졌을때, 해당 prefix 와 suffix 를 동시에 가지고 있는 단어 인덱스를 반환해야한다. 만약 유효한 인덱스가 여러개 이면 최대값을 반환한다.

풀이 (HashMap)

가능한 모든 접두사, 접미사 조합을 HashMap 의 key 로 담아둔다. 그리고 배열에서 몇번째 단어에 해당하는지 인덱스를 value 로 담아둔다.

String[] words = {"apple"};

// hashMap
{
  "a#e": 0,
  "a#le": 0,
  "a#ple": 0,
  "a#pple": 0,
  "a#apple": 0,
  "ap#e": 0,
  "ap#le": 0,
  "ap#ple": 0,
  "ap#pple": 0,
  "ap#apple": 0,
  "app#e": 0,
  "app#le": 0,
  "app#ple": 0,
  "app#pple": 0,
  "app#apple": 0,
  "appl#e": 0,
  "appl#le": 0,
  "appl#ple": 0,
  "appl#pple": 0,
  "appl#apple": 0,
  "apple#e": 0,
  "apple#le": 0,
  "apple#ple": 0,
  "apple#pple": 0,
  "apple#apple": 0
}

class WordFilter {
    private Map<String, Integer> map = new HashMap<>();
    
    public WordFilter(String[] words) {
        for (int i = 0; i < words.length; i++) {
          String word = words[i];
          int length = word.length();
          for (int j = 1; j <= length; j++) {
            for (int k = 1; k <= length; k++) {
              String key = word.substring(0, j) + "{" + word.substring(length - k);
              map.put(key, i);
            }
          }
        }
    }
    
    public int f(String pref, String suff) {
        String s = pref + "{" + suff;
        return map.getOrDefault(s, -1);
    }
}

/**
 * Your WordFilter object will be instantiated and called as such:
 * WordFilter obj = new WordFilter(words);
 * int param_1 = obj.f(pref,suff);
 */

시간복잡도

1. 생성자(WordFilter) 단어의 길이가 L 이면 한 단어에 대해 가능한 조합 수는 접두사와 접미사가 각각 L 개 이므로 L^2 이 된다. N 개의 단어가 있을때 시간 복잡도는 O(N * L^2) 이 된다.

2. 쿼리 메소드(f) 해시맵 키에 정확히 맞는 값으로 조회하기 때문에 O(1) 이다.

풀이 (Trie)

class TrieNode {
  Map<Character, TrieNode> children;
  int index;

  public TrieNode() {
    children = new HashMap<>();
    index = -1;
  }
}

class WordFilter {
  private TrieNode root;

  public WordFilter(String[] words) {
    root = new TrieNode();
    int n = words.length;
    for (int i = 0; i < n; i++) {
      String word = words[i];
      int len = word.length();
      // 모든 prefix와 suffix 조합을 저장
      for (int j = 0; j <= len; j++) {
        String modifiedWord = word.substring(j) + "{" + word;
        insert(modifiedWord, i);
      }
    }
  }

  private void insert(String word, int index) {
    TrieNode current = root;
    for (char ch : word.toCharArray()) {
      current = current.children.computeIfAbsent(ch, c -> new TrieNode());
      current.index = index; // 현재 노드에 가장 큰 인덱스 저장
    }
  }

  public int f(String prefix, String suffix) {
    String searchWord = suffix + "{" + prefix;
    TrieNode current = root;
    for (char ch : searchWord.toCharArray()) {
      current = current.children.get(ch);
      if (current == null) {
        return -1;
      }
    }
    return current.index;
  }
}