add 791

fishercoder1534 · fishercoder1534 · commit 7d2e3b23e5e4 · 2018-03-10T08:35:39.000-08:00
diff --git a/README.md b/README.md
@@ -22,6 +22,7 @@ Your ideas/fixes/algorithms are more than welcome!
 
 |  #  |      Title     |   Solutions   | Time          | Space         | Video  | Difficulty  | Tag                   
 |-----|----------------|---------------|---------------|---------------|--------|-------------|-------------
+|791|[Custom Sort String](https://leetcode.com/problems/custom-sort-string/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_791.java) | O(n+m) | O(1) | |Medium|
 |788|[Rotated Digits](https://leetcode.com/problems/rotated-digits/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_788.java) | O(n*m) | O(1) | |Easy|
 |784|[Letter Case Permutation](https://leetcode.com/problems/letter-case-permutation/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_784.java) | O(n*2^n) | O(n*2^n) | |Easy|
 |783|[Minimum Distance Between BST Nodes](https://leetcode.com/problems/minimum-distance-between-bst-nodes/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_783.java) | O(n) | O(h) | |Easy|
diff --git a/src/main/java/com/fishercoder/solutions/_791.java b/src/main/java/com/fishercoder/solutions/_791.java
@@ -0,0 +1,57 @@
+package com.fishercoder.solutions;
+
+import java.util.HashMap;
+import java.util.Map;
+
+/**
+ * 791. Custom Sort String
+
+ S and T are strings composed of lowercase letters. In S, no letter occurs more than once.
+
+ S was sorted in some custom order previously. We want to permute the characters of T so that they match the order that S was sorted. More specifically, if x occurs before y in S, then x should occur before y in the returned string.
+
+ Return any permutation of T (as a string) that satisfies this property.
+
+ Example :
+ Input:
+ S = "cba"
+ T = "abcd"
+ Output: "cbad"
+ Explanation:
+ "a", "b", "c" appear in S, so the order of "a", "b", "c" should be "c", "b", and "a".
+ Since "d" does not appear in S, it can be at any position in T. "dcba", "cdba", "cbda" are also valid outputs.
+
+ Note:
+
+ S has length at most 26, and no character is repeated in S.
+ T has length at most 200.
+ S and T consist of lowercase letters only.
+
+ */
+public class _791 {
+  public static class Solution1 {
+    public String customSortString(String S, String T) {
+      Map<Character, Integer> map = new HashMap<>();
+      for (char c : T.toCharArray()) {
+        map.put(c, map.getOrDefault(c, 0) + 1);
+      }
+      StringBuilder sb = new StringBuilder();
+      for (char c : S.toCharArray()) {
+        if (map.containsKey(c)) {
+          int count = map.get(c);
+          while (count-- > 0) {
+            sb.append(c);
+          }
+          map.remove(c);
+        }
+      }
+      for (char c : map.keySet()) {
+        int count = map.get(c);
+        while (count-- > 0) {
+          sb.append(c);
+        }
+      }
+      return sb.toString();
+    }
+  }
+}
diff --git a/src/test/java/com/fishercoder/_791Test.java b/src/test/java/com/fishercoder/_791Test.java
@@ -0,0 +1,21 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._791;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _791Test {
+  private static _791.Solution1 solution1;
+
+  @BeforeClass
+  public static void setup() {
+    solution1 = new _791.Solution1();
+  }
+
+  @Test
+  public void test1() {
+    assertEquals("cbad", solution1.customSortString("cba", "abcd"));
+  }
+}
