fd

dingjikerbo · dingjikerbo · commit 2a01dfefd1ee · 2018-12-05T08:27:42.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||
+|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||
 |929|[Unique Email Addresses](https://leetcode.com/problems/unique-email-addresses/)|[Java](leetcode/solution/src/UniqueEmailAddresses.java)|90||
diff --git a/leetcode/solution/src/BackspaceStringCompare.java b/leetcode/solution/src/BackspaceStringCompare.java
@@ -0,0 +1,35 @@
+import java.util.Stack;
+
+public class BackspaceStringCompare {
+
+    public boolean backspaceCompare(String S, String T) {
+        Stack<Character> stack1 = new Stack<>();
+        Stack<Character> stack2 = new Stack<>();
+        for (int i = 0; i < S.length(); i++) {
+            helper(stack1, S, i);
+        }
+        for (int i = 0; i < T.length(); i++) {
+            helper(stack2, T, i);
+        }
+        while (!stack1.isEmpty() && !stack2.isEmpty()) {
+            if (!stack1.pop().equals(stack2.pop())) {
+                return false;
+            }
+        }
+        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();
+            }
+        } else {
+            stack.push(c);
+        }
+    }
+}
diff --git a/leetcode/src/Main.java b/leetcode/src/Main.java
@@ -4,45 +4,37 @@
 
 public class Main {
 
-    static class Man {
-        int quality;
-        int wage;
-
-        Man(int a, int b) {
-            quality = a;
-            wage = b;
-        }
-
-        double ratio() {
-            return (double) wage / quality;
-        }
-    }
-
     public static class Solution {
-        public double mincostToHireWorkers(int[] quality, int[] wage, int K) {
-            Queue<Man> queue = new PriorityQueue<>(new Comparator<Man>() {
-                @Override
-                public int compare(Man o1, Man o2) {
-                    return o1.ratio() > o2.ratio() ? 1 : -1;
-                }
-            });
-            for (int i = 0; i < quality.length; i++) {
-                queue.offer(new Man(quality[i], wage[i]));
+        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);
             }
-            double money = Integer.MAX_VALUE, qsum = 0;
-            Queue<Integer> queue2 = new PriorityQueue<>(Comparator.reverseOrder());
-            while (!queue.isEmpty()) {
-                Man man = queue.poll();
-                qsum += man.quality;
-                queue2.offer(man.quality);
-                if (queue2.size() > K) {
-                    qsum -= queue2.poll();
+            while (!stack1.isEmpty() && !stack2.isEmpty()) {
+                if (!stack1.pop().equals(stack2.pop())) {
+                    return false;
                 }
-                if (queue2.size() == K) {
-                    money = Math.min(money, qsum * man.ratio());
+            }
+            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();
                 }
+            } else {
+                stack.push(c);
             }
-            return money;
         }
     }
 
