[Algorithm Champions] Week 5, No.1

문제

---

풀이

1. smallStrings 의 요소들을 trie에 넣는다.

2. bigString을 한 문자씩 스캔 -> 해당 문자가 트라이에 있는지 확인

3. smallStrings의 크기만큼 해시맵을 만든다. Map<String, Boolean> string = word, boolean = true

4. 쭉 같은지 보다가 마지막 문자라면 해당 단어를 찾았다는 뜻 -> 결과(boolean)를 해시맵에 현재까지 검색한 단어와 함께 저장한다. <단어, 결과>

5. 결과를 저장할 배열을 smallStrings의 길이만큼 만든다.
   smallStrings를 돌면서 각 요소가 맵에 있는지 검색한다.
   맵에 존재한다면 해당 단어를 찾았다는 뜻이니, 결과 배열에 true를 넣는다.
   맵에 존재하지 않는다면 해당 단어를 못찾았다는 것이므로 결과 배열에 false를 넣는다.

6. 마지막으로 결과 배열을 반환한다.

---

코드

package com.company.w5;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/*
date: 21.07.16  21:05 ~ 22:05

I: String, string array
O: array of boolean
C: input - bigString: 모든 문자 숫자 특수문자 다 가능
           array: 0 <= 길이 <= 무한~
E: input array.length == 0 || bigString == "" => return {};
    공백도 문자로 취급해서 다뤄줘야 한다.

1. smallStrings 의 요소들을 trie에 넣는다.
2. bigString을 한 문자씩 스캔 -> 해당 문자가 트라이에 있는지 확인
3. 쭉 같은지 보다가 마지막 문자라면 해당 단어를 찾았다는 뜻 -> 결과(boolean)을 맞는 인덱스에 저장
4. smallStrings의 크기만큼 해시맵을 만든다. Map<String, Boolean> string = word, boolean = true
5. 생성된 맵을 하나씩 본다. & 결과 배열을 만들어서 인덱스 하나씩
    맵에 있는 키값 - smallStrings의 인덱스랑 -> 인덱스 찾기
    맵 안의 boolean 이 true가 아니다 (null) -> 단어를 찾지 못했다는 뜻
    -> 결과 배열에 해당되는 인덱스에 true가 있다면 true를 넣고, 값이 없다면 false를 넣기

bigString = "this is a big string"
smallStrings = this  yo  is  a  bigger  big  string  kappa

     - t - h - i - s(*)
root - y - o(*)
     - i - s(*)
     - a(*)
     - b - i - g(*) - g - e - r(*)
     - s - t - r - i - n - g(*)
     - k - a - p - p - a(*)

class TrieNode{
    Map<Character, TrieNode> children;
    boolean isEnd;
}


this is a big string
                    ^

map <this, true> <is, true> <a, true> <string, true>

iter smallStrings

    result[true, false, true, true, false, true, false]

 */
public class No1 {
    public static void main(String[] args) {
        String bigString = "this is a big string";
        String[] smallStrings = {"this", "yo", "is", "a", "bigger", "string", "kappa"};
        System.out.println(Arrays.toString(isContain(bigString, smallStrings)));
    }

    public static boolean[] isContain(String bigString, String[] smallStrings) {
        Trie1 trie = new Trie1();
        Map<String, Boolean> isContainMap = new HashMap<>();
        boolean[] resultList = new boolean[smallStrings.length];
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < smallStrings.length; i++) {
            trie.insert(smallStrings[i]);
        }

        TrieNode1 node = trie.root;
        Map<Character, TrieNode1> children = node.getChildren();

        for (int i = 0; i < bigString.length(); i++) {
            char curLetter = bigString.charAt(i);
            sb.append(curLetter);

            if (children.containsKey(curLetter)) {
                node = children.get(curLetter);
                if (node.isEnd()) {
                    isContainMap.put(sb.toString(), true);
                    node = trie.root;
                    sb = new StringBuilder();
                }
                children = node.getChildren();
            } else {
                node = trie.root;
                sb = new StringBuilder();
                children = node.getChildren();
            }
        }

        for (int i = 0; i < smallStrings.length; i++) {
            String curWord = smallStrings[i];
            if (isContainMap.containsKey(curWord)) {
                resultList[i] = true;
            } else {
                resultList[i] = false;
            }
        }

        return resultList;
    }
}

class Trie1 {
    TrieNode1 root;

    Trie1() {
        root = new TrieNode1();
    }

    public void insert(String word) {
        TrieNode1 node = root;
        Map<Character, TrieNode1> children = node.getChildren();

        for (int i = 0; i < word.length(); i++) {
            char curLetter = word.charAt(i);

            if (children.containsKey(curLetter)) {
                node = children.get(curLetter);
            } else {
                node = new TrieNode1();
                children.put(curLetter, node);
            }
            children = node.getChildren();
        }
        node.setEnd();
    }
}

class TrieNode1 {
    Map<Character, TrieNode1> children;
    boolean isEnd;

    TrieNode1() {
        children = new HashMap<>();
    }

    public Map<Character, TrieNode1> getChildren() {
        return this.children;
    }

    public void setEnd() {
        this.isEnd = true;
    }

    public boolean isEnd() {
        return this.isEnd;
    }
}