fd

liwentian · liwentian · commit 159f0e775712 · 2017-09-01T21:19:52.000+08:00
diff --git a/README.md b/README.md
@@ -243,6 +243,7 @@
 |316|[Remove Duplicate Letters](https://leetcode.com/problems/remove-duplicate-letters/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/RemoveDuplicateLetters.java)|70|
 |317|[Shortest Distance from All Buildings](https://leetcode.com/problems/shortest-distance-from-all-buildings/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/ShortestDistanceFromAllBuildings.java)|75|典型的bfs，多做两遍|
 |319|[Bulb Switcher](https://leetcode.com/problems/bulb-switcher/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/BulbSwitcher.java)|90|
+|320|[Generalized Abbreviation](https://leetcode.com/problems/generalized-abbreviation/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/GeneralizedAbbreviation.java)|70|这题是典型的back tracking，多做几遍|
 |323|[Number of Connected Components in an Undirected Graph](https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/NumberOfConnectedComponents.java)||
 |324|[Wiggle Sort II](https://leetcode.com/problems/wiggle-sort-ii/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/WiggleSortII.java)|60|
 |325|[Maximum Size Subarray Sum Equals k](https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/MaximumSizeSubarraySumEqualsK.java)|75|这题思路有意思，多做几遍|
diff --git a/google/src/main/java/com/leetcode/google/GeneralizedAbbreviation.java b/google/src/main/java/com/leetcode/google/GeneralizedAbbreviation.java
@@ -0,0 +1,30 @@
+package com.leetcode.google;
+
+import java.util.LinkedList;
+import java.util.List;
+
+/**
+ * Created by liwentian on 2017/9/1.
+ */
+
+public class GeneralizedAbbreviation {
+
+    public List<String> generateAbbreviations(String word) {
+        List<String> list = new LinkedList<>();
+        helper(word, 0, list, "", 0);
+        return list;
+    }
+
+    private void helper(String word, int idx, List<String> list, String cur, int count) {
+        if (idx == word.length()) {
+            if (count > 0) {
+                cur += count;
+            }
+            list.add(cur);
+            return;
+        }
+
+        helper(word, idx + 1, list, cur, count + 1);
+        helper(word, idx + 1, list, cur + (count > 0 ? count : "") + word.charAt(idx), 0);
+    }
+}
diff --git a/solution/src/main/java/com/inuker/solution/GeneralizedAbbreviation.java b/solution/src/main/java/com/inuker/solution/GeneralizedAbbreviation.java
@@ -1,14 +1,34 @@
 package com.inuker.solution;
 
+import java.util.LinkedList;
 import java.util.List;
 
 /**
  * Created by liwentian on 2016/12/29.
  */
 
+/**
+ * https://leetcode.com/articles/generalized-abbreviation/
+ * 思路就是back tracking，对于每个字母，到底是选择留下还是缩写
+ */
 public class GeneralizedAbbreviation {
 
     public List<String> generateAbbreviations(String word) {
-        return null;
+        List<String> list = new LinkedList<>();
+        helper(word, 0, list, "", 0);
+        return list;
+    }
+
+    private void helper(String word, int idx, List<String> list, String cur, int count) {
+        if (idx == word.length()) {
+            if (count > 0) {
+                cur += count;
+            }
+            list.add(cur);
+            return;
+        }
+
+        helper(word, idx + 1, list, cur, count + 1);
+        helper(word, idx + 1, list, cur + (count > 0 ? count : "") + word.charAt(idx), 0);
     }
 }
