93. Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given “25525511135”,

return [“255.255.11.135”, “255.255.111.35”]. (Order does not matter)

思路： 有效的IP地址由4段构成，每段最多3位数，数字在[0,255]区间范围内。
首先我们要对输入做些基本的边界判断，例如s是否为null， 4<=s.length()<=12.
我们可以用一个临时list来盛放每段的ip地址，最后把list 转化为String加入到最终结果List里面；
递归结束条件: 满足保存ip地址的临时list.size() == 4的情况下: 1. 记录当前位置的pos正好为给定字符串s的长度，否的话，返回； 2. 满足以上两个条件，就是一个合理解，把临时list转化为String加到最终结果List里面；
递归条件：从i=pos开始，到i < s.length() && i < pos + 3进行遍历，这是因为每段ip最多为3位数字构成； 对于每次求得的当前ip segment = s.substring(i, pos + 1); 调用isValid判断是否是合理的ip segment， 合理的话，加入到临时list；递归调用执行i+1步求解， 最后别忘了list中去除最后一个元素。

复杂度：

public class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        if (s == null || s.length() < 4 || s.length() > 12) return res;
        helper(res, s, 0, new ArrayList<String>());
        return res;
    }

    public void helper(List<String> res, String s, int pos, List<String> ipList) {
        if (ipList.size() == 4) {
            if (pos != s.length()) return;
            res.add(convertListToString(ipList));
            return;
        }

        for (int i = pos; i < s.length() && i < pos + 3; i++) {
            String ipSeg = s.substring(pos, i+1);
            if (isValid(ipSeg)) {
                ipList.add(ipSeg);
                helper(res, s, i + 1, ipList);
                ipList.remove(ipList.size() - 1);
            }
        }
    }

    private boolean isValid(String s) {
        if (s == null || s.length() == 0) return false;
        if (s.charAt(0) == '0') {
            return s.equals("0");
        }
        int num = Integer.parseInt(s);
        return num > 0 && num < 256;
    }

    private String convertListToString(List<String> list) {
        StringBuilder sb = new StringBuilder();
        for (String s: list) {
            sb.append(s);
            sb.append(".");
        }
        String ipAddress = sb.toString();
        return ipAddress.substring(0, ipAddress.length() - 1);
    }
}

Reference:
https://segmentfault.com/a/1190000006245389

http://www.cnblogs.com/yrbbest/p/4437164.html

22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

思路: 递归， 左括号个数用left表示， 右括号用right表示；
递归终止条件： left == n && right == n
递归过程： 先加入左括号, 条件为left right)

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        if (n <= 0) return res;
        helper("", res, 0, 0, n);
        return res;
    }

    public void helper(String tmp, List<String> res, int left, int right, int n) {
        if (left == n && right == n) {
            res.add(tmp);
            return;
        }
        if (left < n) {
            helper(tmp + "(", res, left + 1, right, n);
        }
        if (right < left) {
            helper(tmp + ")", res, left, right + 1, n);
        }
    }
}

Follow up: 缩进输出
借鉴解法： 替换 left== n && right == n

int level = 0;
for(int i = 0; i < tmp.length(); i++){
    if(tmp.charAt(i) == '{'){
        for(int k = 0; k < level; k++){
            System.out.print('\t');
        }
        System.out.println('{');
        level++;
    } else {
        level--;
        for(int k = 0; k < level; k++){
            System.out.print('\t');
        }
        System.out.println('}');
    }
}

79. Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word = “ABCCED”, -> returns true,
word = “SEE”, -> returns true,
word = “ABCB”, -> returns false.

思路: Backtracking 的方法来解决这道题目。我们需要先从board中找到第一个字符出现的位置，然后从这个位置开始往上，下，左，右开始寻找；这里我们要借助一个dfs(x,y, index, board, word)的函数来寻找； 当index==word.length的时候就找到了对应的字符，返回true; 注意边界条件的check，x,y要保证在board内，或者当board[x][y]!=word.charAt(index)的时候都返回false。
复杂度： Time复杂度: 遍历整个m * n 的board的时间复杂度为m * n,对于每个点都会往上下左右来遍历寻找， k为word长度，大概要遍历4^k次，所以总的时间复杂度大概在mn4^k.
Space： 由于word长度为k，recursive space大概在O(k).

public class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || board[0] == null || board.length == 0 || board[0].length == 0 || word == null) return false;
        // find the first char of word in board
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (word.charAt(0) == board[i][j]) {
                    if (dfs(i, j, 0, board, word )) {
                        return true;
                    }
                }

            }
        }
        return false;
    }

    public boolean dfs(int x, int y, int index, char[][] board, String word) {
        if (index == word.length()) {
            return true;
        }
        if (x < 0 || y < 0 || x >= board.length || y >= board[0].length || board[x][y] != word.charAt(index)) 
            return false;
        char tmp = board[x][y]; // save the point's value
        board[x][y] = '#'; // mark the point first
        boolean flag = dfs(x - 1, y, index + 1, board, word) ||
                       dfs(x, y - 1, index + 1, board, word) ||
                       dfs(x + 1, y, index + 1, board, word) ||
                       dfs(x, y + 1, index + 1, board, word);
        board[x][y] = tmp;
        return flag;
    }
}

133. Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ’s undirected graph serialization:
Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:

     1
      / \
     /   \
    0 --- 2
         / \
         \_/

思路：图的基础题目， 用DFS或者BFS 来做。
要利用HashMap来建立个从原节点到克隆节点的map，用来判断我们是否克隆过某个节点。

DFS:

public class Solution {
    HashMap<Integer, UndirectedGraphNode> map = new HashMap<>();
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) return node;
        if (map.containsKey(node.label)) 
            return map.get(node.label);
        // init the clone node
        UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
        map.put(node.label, newNode);
        // iterate origin node's neighbor and clone it
        for (UndirectedGraphNode n: node.neighbors) {
            newNode.neighbors.add(cloneGraph(n));
        }
        return newNode;
    }
}

BFS:

public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) return node;
        HashMap<Integer, UndirectedGraphNode> visited = new HashMap<>();
        Deque<UndirectedGraphNode> queue = new ArrayDeque<>();
        UndirectedGraphNode newNode= new UndirectedGraphNode(node.label);
        visited.put(node.label, newNode);
        queue.offer(node);
        while(!queue.isEmpty()) {
            UndirectedGraphNode cur = queue.poll();
            for (UndirectedGraphNode n : cur.neighbors) {
                if (!visited.containsKey(n.label)) {
                    queue.offer(n);
                    visited.put(n.label, new UndirectedGraphNode(n.label));
                }
                visited.get(cur.label).neighbors.add(visited.get(n.label));
            }
        }
        return visited.get(node.label);
    }
}