843. Guess the Word

T: O(10*n*6), n is word list len
S: O(n)

/**
 * // This is the Master's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface Master {
 *     public int guess(String word) {}
 * }
 */
class Solution {
    public void findSecretWord(String[] wordlist, Master master) {
        
        Random random = new Random();
        List<String> words = new ArrayList<>(Arrays.asList(wordlist));
        
        for (int i = 0; i < 10; i++) { // try 10 times
            int ranIdx = random.nextInt(words.size());
            String pickedWord = words.get(ranIdx);
            
            int matchedCount = master.guess(pickedWord);
            if (matchedCount == 6) { // guess success!
                return;
            }
            // narrow the word lists, so we have a new words list (size is smaller
            words = getSimilarWords(pickedWord, words, matchedCount);
        }
    }
    private List<String> getSimilarWords(String s, List<String> words, int matchedCount) {
        List<String> res = new ArrayList<>();
        char[] sAry = s.toCharArray();
        
        for (String word : words) {
            char[] w = word.toCharArray();
            int count = 0;
            for (int i = 0; i < sAry.length; i++) {
                if (sAry[i] == w[i]) {
                    count++;
                }
            }
            // filter not similar words, only add similar words
            if (count == matchedCount) {
                res.add(word);
            }
        }
        return res;
    }
}

/*
if we want to pass test within 10 times
try to narrow the wordlist

pick one string from wordlist to guess matches number
if (matches == 6) got ans! break from the loop or return

fiter wordlist's matches not equal to the matches number we got

repeat do this

T: O(10*n*6), n is word list len
S: O(n)
*/