class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 1) {
            return strs[0];
        }
        int min = 201;
        for (int i = 0; i < strs.length; i++) {
            if(strs[i] == ""){
                return "";
            }
            min = min < strs[i].length() ? min : strs[i].length();
        }
        int left = 0;
        int right = min - 1;
        boolean flag;
        int mid = 0;
        while (left <= right) {
            flag = true;
            mid = (left + right) / 2;
            String str = strs[0].substring(left,mid+1);
            for (int i = 0; i < strs.length; i++) {
                String temp = strs[i].substring(left,mid+1);
                if (!str.equals(strs[i].substring(left,mid+1))) {
                    flag = false;
                    break;
                }
            }
            if(left == right){
                if(flag){
                    return strs[0].substring(0, mid+1);
                }else {
                    if(left == 0){
                        return "";
                    }
                    return strs[0].substring(0, mid);
                }
            }
            if (flag) {
                left = mid + 1 > right ? right : mid + 1;
            } else {
                right = mid - 1 < left ? left : mid -1;
            }
        }
        return "";
    }
}

class Trie {
    HashSet<String> set = new HashSet<>();
    public Trie() {

    }
    public void insert(String word) {
        set.add(word);
    }
    public boolean search(String word) {
        return set.contains(word);
    }
    public boolean startsWith(String prefix) {
        for (String s : set) {
            if(s.startsWith(prefix)) return true;
        }
        return false;
    }
}