@@ -1,5 +1,5 @@
 M
-1516696879
+1533626601
 tags: Hash Table
 
 #### Based on 2sum
@@ -44,26 +44,25 @@ Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b
 2nd part: try [i + 1, end], see if any combination sum that makes: target - sum exist in map. -> becomes same old 2sum problem.
 O(n)
 */
-/*
-Thoughts:
-Can't do for loop over 3sum, which is O(n^3), not doable.
-We can break the nums into 2 major parts by index i.
-1st part: from [0 ~ i], we'll try all possible ways to pair [x, i] and store the sum of nums[x]+nums[i] in map. 
-Note: key is sum, and the value is a hashSet of ArrayList. Where the hashset has itself functions to tell duplicate of pairs.
-2nd part: try [i + 1, end], see if any combination sum that makes: target - sum exist in map. -> becomes same old 2sum problem.
+/**
+  Why having below front-pair-building after previous for end-pair-checking for loop?
+  Here: we build [0 ~ i], and in next round, when we processs [i + 1, end], pairs built among [0~i] below will all be used.
+  Rather: if we have lift the for loop below to calculate [0~i] before the end-pair-checking of same [i~end], 
+          there is one index at [i] will overlap, which turns to be incorrect.
+  Therefore, we build front-pairs aftwarwards: it's building [0~i] here, which aims to help next round of end-pair-checking on [i+1, end].
 */
 class Solution {
     public List<List<Integer>> fourSum(int[] nums, int target) {
         List<List<Integer>> result = new ArrayList<>();
-        if (nums == null || nums.length <= 3) {
-            return result;
-        }
+        if (nums == null || nums.length <= 3) return result;
+        
+        int n = nums.length;
         Arrays.sort(nums);
         Map<Integer, HashSet<List>> map = new HashMap<>();
         Set<String> cache = new HashSet<>();
-        for (int i = 0; i < nums.length; i++) {
+        for (int i = 0; i < n; i++) {
             // Check if [i + 1, end] can be added up to target
-            for (int k = i + 1; k < nums.length; k++) {
+            for (int k = i + 1; k < n; k++) {
                 int sum = nums[i] + nums[k];
                 if (map.containsKey(target - sum)) {// Try to match up the 4 pairs
                     for (List<Integer> frontPair : map.get(target - sum)) {
@@ -76,19 +75,11 @@ public List<List<Integer>> fourSum(int[] nums, int target) {
                     }
                 }
             }
-            /**
-              Why having below front-pair-building after previous for end-pair-checking for loop?
-              Here: we build [0 ~ i], and in next round, when we processs [i + 1, end], pairs built among [0~i] below will all be used.
-              Rather: if we have lift the for loop below to calculate [0~i] before the end-pair-checking of same [i~end], 
-                      there is one index at [i] will overlap, which turns to be incorrect.
-              Therefore, we build front-pairs aftwarwards: it's building [0~i] here, which aims to help next round of end-pair-checking on [i+1, end].
-             */
+            
             // Build up the pair from [0 ~ i]
             for (int j = 0; j < i; j++) {
                 int sum = nums[j] + nums[i];
-                if (!map.containsKey(sum)) {
-                    map.put(sum, new HashSet<>());
-                }
+                map.putIfAbsent(sum, new HashSet<>());
                 map.get(sum).add(Arrays.asList(nums[j], nums[i]));
             }
         }
@@ -101,6 +92,9 @@ private String buildKey(List<Integer> list) {
         return sb.toString();
     }
 }
+
+  
+  
 /*
 Thoughts
 Perform another layer outside of 3SUM. O(n^3).
 
@@ -14,7 +14,7 @@
 - 什么时候会积累profit呢? 
 - 1. 原本就持有股票的, 如果毫无动作, 那么状态不变, 积累profit diff. 
 - 2. 卖出了股票, 状态改变, 积累profit diff.
-- 注意: 只有在状态index: 0, 2, 4, 也就是卖掉股票的时候, 猜可以积累profit
+- 注意: 只有在状态index: 0, 2, 4, 也就是卖掉股票的时候, 才可以积累profit
 
 ##### Rolling Array
 - [i] 只有和 [i-1] 打交道, reduce space
@@ -80,13 +80,13 @@ public int maxProfit(int[] prices) {
         for (int i = 1; i < n; i++) {
             for (int j = 1; j < 5; j++) {
                 // Accumulate partial profit regardless of stock status.
-                int dailyPartialProfit = prices[i] - prices[i - 1];
+                int dailyDiff = prices[i] - prices[i - 1];
                 if (j % 2 == 0) { // j status: no stock
-                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + dailyPartialProfit);
+                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + dailyDiff);
                     // Find best profit when not having stock
                     profit = Math.max(profit, dp[i][j]);
                 } else { // j status: have stock
-                    dp[i][j] = Math.max(dp[i - 1][j] + dailyPartialProfit, dp[i - 1][j - 1]);
+                    dp[i][j] = Math.max(dp[i - 1][j] + dailyDiff, dp[i - 1][j - 1]);
                 }
             }
         }
 
@@ -11,6 +11,7 @@
 #### BFS
 - 应该比较好想: naturally level-traverse all nodes, add node to appropriate col list
 - Use min/max to track map keys, since the keys are continous
+- Map does not provide random access; unless map key is marked with sequence i = [min, max]
 
 #### DFS
 - 一开始很容易想到: enumerate一下, 先放curr node.val, 然后node.left.val, node.right.val. 非常简单
 
@@ -62,7 +62,7 @@ public int compare(String s1, String s2) {
             }
         });
 
-        StringBuffer sb =  new StringBuffer();
+        StringBuffer sb = new StringBuffer();
         for (int i = 0; i < num.length; i++) {
             sb.append(strs[i]);
         }
 
@@ -85,7 +85,7 @@ public int lengthOfLongestSubstring(String s) {
         for (int i = 0; i < arr.length; i++) {
             char c = arr[i];
             if (map.containsKey(c)) {
-                i = map.get(c);
+                i = map.get(c); // reset beginning
                 map = new HashMap<>();
             } else {
                 map.put(c, i);
 
@@ -1,5 +1,5 @@
 H
-1528263371
+1533619954
 tags: Array, Binary Search, Divide and Conquer, DFS
 
 著名的找两个sorted array的中位数. 中位数定义: 如果两个array总长为偶数, 取平均值.
@@ -17,8 +17,6 @@
 - 2. 如果 k == 1: 就是找A/B 里面的1st item, 那么做个 `Math.max(A[startA], B[startB])` 就可以
 - 总共的数字长度是 (m + n) 而且每次都有一般的内容被删除, 那么time就是 O(log(m + n))
 
-#### Binary Search
-TODO:
 
 ```
 /*
@@ -88,17 +86,11 @@ public double findMedianSortedArrays(int[] numsA, int[] numsB) {
     // Find kth number in two sorted array. k is size
     private int findKth(int[] numsA, int startA, int[] numsB, int startB, int k) {
         // check edge case for startA/startB index
-        if (startA >= numsA.length) {
-            return numsB[startB + k - 1];
-        }
-        if (startB >= numsB.length) {
-            return numsA[startA + k - 1];
-        }
+        if (startA >= numsA.length) return numsB[startB + k - 1]; // A exhausted, take kth in B
+        if (startB >= numsB.length) return numsA[startA + k - 1]; // B exhausted, take kth in A
 
-        // handle final condition k == 1
-        if (k == 1) {
-            return Math.min(numsA[startA], numsB[startB]);
-        }
+        // handle final condition k == 1. The two elements will be sorted and the smaller one is kth.
+        if (k == 1) return Math.min(numsA[startA], numsB[startB]);
 
         // compare and partition at each [x+(k/2-1)] position
         int halfKthOfA = startA + k / 2 - 1 < numsA.length ? numsA[startA + k / 2 - 1] : Integer.MAX_VALUE;
 
@@ -51,14 +51,13 @@
 class Solution {
     public List<List<String>> solveNQueens(int n) {
         List<List<String>> rst = new ArrayList<>();
-        if (n <= 0) {
-            return rst;
-        }
+        if (n <= 0) return rst;
+
         dfs(rst, new ArrayList<>(), n);
 
         return rst;
     }
-
+    // build sequence row
     private void dfs(List<List<String>> rst, List<Integer> list, int n){
         if (list.size() == n) {
             rst.add(createBoard(list));
 
@@ -1,12 +1,12 @@
 M
-1522215963
+1533623972
 tags: String
 
 如果S, T只用一个operation就能变成相等, return true.
 
 #### Edit: 删除，增加，和替换
 - 换完之后，理论上换成的String 就应该全等
-- for loop, 一旦找到不一样的char, 就判断那三种可能性
+- for loop, 一旦找到不一样的char, 就判断那三种可能性: insert/delete/replace
 - insert/delete 对于2个string来说, 效果是类似的
 - O(n)
 
@@ -15,6 +15,25 @@
 Given two strings S and T, determine if they are both one edit distance apart.
 
 */
+class Solution {
+    public boolean isOneEditDistance(String s, String t) {
+        if (s == null || t == null || s.equals(t) || Math.abs(s.length() - t.length()) > 1) {
+            return false;
+        }
+        int size = Math.min(s.length(), t.length());
+        for (int i = 0; i < size; i++) {
+            if (s.charAt(i) != t.charAt(i)) { // check insert/delete or replace
+                return compareStr(s, t, i + 1, i) || compareStr(s, t, i, i + 1) || compareStr(s, t, i + 1, i + 1);
+            }
+        }
+        
+        return true; // size == 0, and length diff == 1
+    }
+    
+    private boolean compareStr(String s, String t, int x, int y) {
+        return s.substring(x).equals(t.substring(y));
+    }
+}
 
 /*
 Thoughts:
 
@@ -1,9 +1,10 @@
 M
-1528074589
+1533623494
 tags: Backtracking, DFS, Permutation
 
 #### Recursive: Backtracking
 - Given a remaining list: 取, 或者不取
+- always iterate over full `nums[]`, use list.contains() to check if item has been added.
 - Improvement: maintain list (add/remove elements) instead of 'list.contains'
 - time O(n!): visit all possible outcome
 - T(n) = n * T(n-1) + O(1)
@@ -44,6 +45,30 @@
 Recursion Search
 
 */
+class Solution {
+    public List<List<Integer>> permute(int[] nums) {
+        List<List<Integer>> result = new ArrayList<List<Integer>>();
+        if (nums == null || nums.length == 0) {
+            return result;
+        }
+        
+        dfs(result, new ArrayList<>(), nums);
+        return result;
+    }
+    
+    private void dfs(List<List<Integer>> result, List<Integer> levelList, int[] nums) {
+        if (levelList.size() == nums.length) {
+            result.add(new ArrayList<>(levelList));
+            return;
+        }
+        for (int i = 0; i < nums.length; i++) {
+            if (levelList.contains(nums[i])) continue;
+            levelList.add(nums[i]);
+            dfs(result, levelList, nums);
+            levelList.remove(levelList.size() - 1);
+        }
+    }
+}
 
 /*
 Thoughts:
 
@@ -1,15 +1,16 @@
 M
 1531595945
-tags: Array
+tags: Array, PreProduct
 time: O(n)
 space: O(1)
 
 给一串数字, output rst[n], 每个index是 除了nums[i]以外 所有itemd的乘积.
 
-#### Array
+#### Array, PreProduct
 - 分析普通做法, 了结到用从左到右一遍O(n), 从右到左一遍 O(n) 就可以
 - 注意carry的维护
 - 看第二个解答, 进一步简化了代码
+- PreProduct, 跟preSum的感觉有点像, 就是差一位.
 
 ```
 /*
Original file line number	Diff line number	Diff line change
`@@ -62,7 +62,7 @@ public int compare(String s1, String s2) {`
`62`	`62`	`}`
`63`	`63`	`});`
`64`	`64`
`65`		`- StringBuffer sb = new StringBuffer();`
	`65`	`+ StringBuffer sb = new StringBuffer();`
`66`	`66`	`for (int i = 0; i < num.length; i++) {`
`67`	`67`	`sb.append(strs[i]);`
`68`	`68`	`}`