new problem

dingjikerbo · dingjikerbo · commit 0a0e27ca8d39 · 2018-12-05T09:33:00.000+08:00
diff --git a/README.md b/README.md
@@ -393,6 +393,7 @@
 |703|[Kth Largest Element in a Stream](https://leetcode.com/problems/kth-largest-element-in-a-stream/)|[Java](leetcode/solution/src/KthLargestElementInAStream.java)|100||
 |771|[Jewels and Stones](https://leetcode.com/problems/jewels-and-stones/)|[Java](leetcode/solution/src/JewelsAndStones.java)|100||
 |819|[Most Common Word](https://leetcode.com/problems/most-common-word/)|[Java](leetcode/solution/src/MostCommonWord.java)|85||
+|843|[Guess the Word](https://leetcode.com/problems/guess-the-word/)|[Java](leetcode/solution/src/GuessTheWord.java)|90||
 |844|[Backspace String Compare](https://leetcode.com/problems/backspace-string-compare/)|[Java](leetcode/solution/src/BackspaceStringCompare.java)|100||
 |857|[Minimum Cost to Hire K Workers](https://leetcode.com/problems/minimum-cost-to-hire-k-workers/)|[Java](leetcode/solution/src/MinimumCostToHireKWorkers.java|70||
 |904|[Fruit Into Baskets](https://leetcode.com/problems/fruit-into-baskets/)|[Java](leetcode/solution/src/FruitIntoBaskets.java)|90||
diff --git a/leetcode/solution/src/GuessTheWord.java b/leetcode/solution/src/GuessTheWord.java
@@ -0,0 +1,41 @@
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Random;
+
+public class GuessTheWord {
+
+    public interface Master {
+        int guess(String word);
+    }
+
+    /**
+     * 这题的意思是有一个word列表，取其中一个作为secret，现在让你来猜哪个是secret，最多猜10次，
+     * 你每猜一个单词，就告诉你这个单词和secret匹配的字母数。
+     * 这里的思路很直接，就是随机取一个单词开始，获得了匹配的字母数后在单词列表中找到可能的候选项
+     * 然后再迭代一次，这样猜10次
+     */
+    public void findSecretWord(String[] wordlist, Master master) {
+        Random random = new Random();
+        for (int i = 0; i < 10; i++) {
+            String word = wordlist[random.nextInt(wordlist.length)];
+            int match = master.guess(word);
+            List<String> list = new ArrayList<>();
+            for (String s : wordlist) {
+                if (match(s, word) == match) {
+                    list.add(s);
+                }
+            }
+            wordlist = list.toArray(new String[0]);
+        }
+    }
+
+    private int match(String s, String t) {
+        int match = 0;
+        for (int i = 0; i < s.length(); i++) {
+            if (s.charAt(i) == t.charAt(i)) {
+                match++;
+            }
+        }
+        return match;
+    }
+}
diff --git a/leetcode/src/Main.java b/leetcode/src/Main.java
@@ -5,36 +5,35 @@
 public class Main {
 
     public static class Solution {
-        public boolean backspaceCompare(String S, String T) {
-            if (S.length() < T.length()) {
-                return backspaceCompare(T, S);
-            }
-            Stack<Character> stack1 = new Stack<>();
-            Stack<Character> stack2 = new Stack<>();
-            for (int i = 0; i < S.length(); i++) {
-                helper(stack1, S, i);
-                helper(stack2, T, i);
-            }
-            while (!stack1.isEmpty() && !stack2.isEmpty()) {
-                if (!stack1.pop().equals(stack2.pop())) {
-                    return false;
+
+        public interface Master {
+            int guess(String word);
+        }
+
+
+        public void findSecretWord(String[] wordlist, Master master) {
+            Random random = new Random();
+            for (int i = 0; i < 10; i++) {
+                String word = wordlist[random.nextInt(wordlist.length)];
+                int match = master.guess(word);
+                List<String> list = new ArrayList<>();
+                for (String s : wordlist) {
+                    if (match(s, word) == match) {
+                        list.add(s);
+                    }
                 }
+                wordlist = list.toArray(new String[0]);
             }
-            return stack1.isEmpty() && stack2.isEmpty();
         }
 
-        private void helper(Stack<Character> stack, String s, int i) {
-            if (i >= s.length()) {
-                return;
-            }
-            char c = s.charAt(i);
-            if (c == '#') {
-                if (!stack.isEmpty()) {
-                    stack.pop();
+        private int match(String s, String t) {
+            int match = 0;
+            for (int i = 0; i < s.length(); i++) {
+                if (s.charAt(i) == t.charAt(i)) {
+                    match++;
                 }
-            } else {
-                stack.push(c);
             }
+            return match;
         }
     }
 
