fd

liwentian · liwentian · commit f786fe4d94ed · 2017-08-30T11:14:21.000+08:00
diff --git a/google/src/main/java/com/leetcode/google/DecodeString.java b/google/src/main/java/com/leetcode/google/DecodeString.java
@@ -0,0 +1,51 @@
+package com.leetcode.google;
+
+import java.util.Deque;
+import java.util.LinkedList;
+import java.util.Queue;
+import java.util.Stack;
+
+/**
+ * Created by liwentian on 2017/8/30.
+ */
+
+public class DecodeString {
+
+    public String decodeString(String s) {
+        StringBuilder sb = new StringBuilder();
+
+        for (char c : s.toCharArray()) {
+            if (c != ']') {
+                sb.append(c);
+            } else {
+                String t = popString(sb);
+                for (int i = popCount(sb); i > 0; i--) {
+                    sb.append(t);
+                }
+            }
+        }
+
+        return sb.toString();
+    }
+
+    private String popString(StringBuilder sb) {
+        StringBuilder ss = new StringBuilder();
+
+        int i = sb.length() - 1;
+        for ( ; sb.charAt(i) != '['; i--) {
+            ss.append(sb.charAt(i));
+        }
+        sb.setLength(i);
+
+        return ss.reverse().toString();
+    }
+
+    private int popCount(StringBuilder sb) {
+        int i = sb.length() - 1, cnt = 0, t = 1;
+        for ( ; i >= 0 && Character.isDigit(sb.charAt(i)); i--, t *= 10) {
+            cnt += t * (sb.charAt(i) - '0');
+        }
+        sb.setLength(i + 1);
+        return cnt;
+    }
+}
diff --git a/solution/src/main/java/com/inuker/solution/DecodeString.java b/solution/src/main/java/com/inuker/solution/DecodeString.java
@@ -8,66 +8,42 @@
 
 public class DecodeString {
 
-    /**
-     * 两种思路，递归和栈
-     */
-
-    // 耗时3ms，性能很好，思路很直观
-    // 以[]内的为递归对象
-    public String decodeString(String s) {
+    // 耗时3ms，思路很直观，且不容易错，面试推荐写法
+    public String decodeString2(String s) {
         StringBuilder sb = new StringBuilder();
-        for (int i = 0; i < s.length(); i++) {
-            char c = s.charAt(i);
 
-            if (c < '0' || c > '9') {
+        for (char c : s.toCharArray()) {
+            if (c != ']') {
                 sb.append(c);
-                continue;
+            } else {
+                String t = popString(sb);
+                for (int i = popCount(sb); i > 0; i--) {
+                    sb.append(t);
+                }
             }
+        }
 
-            // 先解析数字
-            int index = s.indexOf('[', i + 1);
-            int digit = Integer.valueOf(s.substring(i, index));
-            i = index + 1;
+        return sb.toString();
+    }
 
-            for (int count = 1; count != 0; i++) {
-                if (s.charAt(i) == '[') {
-                    count++;
-                } else if (s.charAt(i) == ']') {
-                    count--;
-                }
-            }
+    private String popString(StringBuilder sb) {
+        StringBuilder ss = new StringBuilder();
 
-            String str = decodeString(s.substring(index + 1, --i));
-            for ( ; digit > 0; digit--, sb.append(str));
+        int i = sb.length() - 1;
+        for ( ; sb.charAt(i) != '['; i--) {
+            ss.append(sb.charAt(i));
         }
+        sb.setLength(i);
 
-        return sb.toString();
+        return ss.reverse().toString();
     }
 
-    // 耗时4ms
-    public String decodeString2(String s) {
-        Stack<Integer> intStack = new Stack<Integer>();
-        Stack<StringBuilder> strStack = new Stack<StringBuilder>();
-        StringBuilder cur = new StringBuilder();
-        for (int i = 0, digit = 0; i < s.length(); i++) {
-            char c = s.charAt(i);
-            if (c >= '0' && c <= '9') {
-                digit = digit * 10 + (c - '0');
-            } else if (c == '[') {
-                intStack.push(digit);
-                digit = 0;
-                strStack.push(cur);
-                cur = new StringBuilder();
-            } else if (c == ']') {
-                StringBuilder tmp = cur;
-                cur = strStack.pop();
-                for (int k = intStack.pop(); k > 0; k--) {
-                    cur.append(tmp);
-                }
-            } else {
-                cur.append(c);
-            }
+    private int popCount(StringBuilder sb) {
+        int i = sb.length() - 1, cnt = 0, t = 1;
+        for ( ; i >= 0 && Character.isDigit(sb.charAt(i)); i--, t *= 10) {
+            cnt += t * (sb.charAt(i) - '0');
         }
-        return cur.toString();
+        sb.setLength(i + 1);
+        return cnt;
     }
 }
diff --git a/test/src/main/java/com/example/Main.java b/test/src/main/java/com/example/Main.java
@@ -1,5 +1,6 @@
 package com.example;
 
+import com.leetcode.google.DecodeString;
 import com.leetcode.google.MissingRanges;
 import com.leetcode.google.SentenceScreenFitting;
 import com.leetcode.google.WordSquares;
@@ -12,12 +13,8 @@
 public class Main {
 
     public static void main(String[] args) {
-        List<String> list = new MissingRanges().findMissingRanges(new int[] {
-                Integer.MIN_VALUE, Integer.MAX_VALUE
-        }, Integer.MIN_VALUE, Integer.MAX_VALUE);
-        for (String s : list) {
-            System.out.println(s);
-        }
+        String s = new DecodeString().decodeString("10[ab]");
+        System.out.println(s);
     }
 }
 
