復原 IP 地址

93. 復原 IP 地址 - 力扣（LeetCode）

有效 IP 地址 正好由四個整數（每個整數位于 0 到 255 之間組成，且不能含有前導 0），整數之間用 '.' 分隔。

• 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 無效 IP 地址。

給定一個只包含數字的字符串 s ，用以表示一個 IP 地址，返回所有可能的有效 IP 地址，這些地址可以通過在 s 中插入 '.' 來形成。你 不能 重新排序或刪除 s 中的任何數字。你可以按 任何 順序返回答案。

示例 1：

輸入：s = "25525511135"
輸出：["255.255.11.135","255.255.111.35"]

示例 2：

輸入：s = "0000"
輸出：["0.0.0.0"]

示例 3：

輸入：s = "101023"
輸出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示：

• 1 <= s.length <= 20
• s 僅由數字組成

解

IP地址只有四段，所以將分割的段數 == 4作為終止條件。考慮到構造IP地址時還要手動給添加三個小數點，所以我們用變量pointCount來表示小數點數量，pointCount == 3說明字符串分成了4段了。

List<String> addressList = new ArrayList<>();public List<String> restoreIpAddresses(String s)
{if(s.length() < 4 || s.length() > 12)return addressList;backTracing(s, 0, 0);return addressList;
}//判斷索引在[start,end]之間的字符能否構造有效的IP的地址
public boolean isValid(String s, int start, int end)
{//避免數組越界if (start > s.length() - 1)return false;//含有前導零if (s.charAt(start) == '0' && start != end)return false;//四位數及以上if (end - start >= 3)return false;int num = 0;for (int i = start; i <= end; i++)num = num * 10 + s.charAt(i) - '0';return num <= 255;
}/*** @param pointCount  . 的個數*/
public void backTracing(String s, int startIndex, int pointCount)
{//若已經分成四段if (pointCount == 3){//若最后一段有效，則記錄一個有效IP地址if (isValid(s, startIndex, s.length() - 1))addressList.add(s);return;}//分段不足則繼續分for (int i = startIndex; i < s.length(); i++){if (isValid(s, startIndex, i)){//用截取、拼接的方法插入 .s = s.substring(0, i + 1) + "." + s.substring(i + 1);pointCount++;//插入 . 后，字符串 s 中下一個數字的索引為 i + 2。//不用擔心越界，因為 s 的長度也變大了backTracing(s, i + 2, pointCount);//撤回 .s = s.substring(0, i + 1) + s.substring(i + 2);pointCount--;}else //若中間有一段無效，那后面的都不用看了break;}
}

電話號碼的字母組合

17. 電話號碼的字母組合 - 力扣（LeetCode）

給定一個僅包含數字 2-9 的字符串，返回所有它能表示的字母組合。答案可以按 任意順序 返回。

給出數字到字母的映射如下（與電話按鍵相同）。注意 1 不對應任何字母。

示例 1：

輸入：digits = "23"
輸出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

輸入：digits = ""
輸出：[]

示例 3：

輸入：digits = "2"
輸出：["a","b","c"]

提示：

• 0 <= digits.length <= 4
• digits[i] 是范圍 ['2', '9'] 的一個數字。

圖解思路

代碼實現

List<String> combinationList = new ArrayList<>();
String digits;//數字到字母的映射
String[] map = {"", "", "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};//更高效的字符串拼接類型
StringBuilder combination = new StringBuilder();public List<String> letterCombinations(String digits)
{if(digits.isEmpty())return combinationList;this.digits = digits;backTracing(0);return combinationList;
}/*** @param numIndex digits中數字 num 的索引*/
public void  backTracing(int numIndex)
{if (numIndex > digits.length() - 1){combinationList.add(combination.toString());return;}//求 num 所映射的字符串String str = map[digits.charAt(numIndex) - '0'];for (int i = 0; i < str.length(); i++){//從 str 中依次選取單個字符combination.append(str.charAt(i));//從 digits 中選擇下一個數字backTracing(numIndex + 1);//撤銷組合中最后一個字符，循環再試（換本層 str 的下一個字符）combination.deleteCharAt(combination.length() - 1);}
}

括號生成

22. 括號生成 - 力扣（LeetCode）

數字 n 代表生成括號的對數，請你設計一個函數，用于能夠生成所有可能的并且 有效的 括號組合。

示例 1：

輸入：n = 3
輸出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

輸入：n = 1
輸出：["()"]

提示：

• 1 <= n <= 8

深搜，做減法

public List<String> generateParenthesis(int n)
{//特判if (n == 0)return null;//結果集ArrayList<String> res = new ArrayList<>();//深搜，找出全部有效括號組合DFS(res, n, n, "");return res;
}/*** @param res 結果集* @param left 左括號還能用幾個* @param right 右括號還能用幾個* @param curStr 當前遞歸所得到的字符串*/
public static void DFS(List<String> res, int left, int right, String curStr)
{//左右括號都用完了；將一種組合添加到結果集if (left == 0 && right == 0){res.add(curStr);return;}//若左括號剩余數量大于右括號剩余數量，則“剪枝”（不再進行這種錯誤模式的括號組合）。if (left > right)return;//若還剩余左括號，則使用左括號if (left > 0)DFS(res, left - 1, right, curStr + "(" );//若還剩余右括號，則使用右括號if (right > 0)DFS(res, left, right - 1, curStr +")" );
}

深搜，做加法

public List<String> generateParenthesis_2(int n)
{//特判if (n == 0)return null;//結果集ArrayList<String> res = new ArrayList<String>();//深搜,尋找全部有效括號組合DFS_2(res, 0, 0, "", n);return res;
}/*** @param res 結果集* @param left 左括號使用了幾個* @param right 右括號使用使用了幾個* @param curStr 當前遞歸所得到的字符串* @param n 題目所給的括號生成對數*/
public static void DFS_2(List<String> res, int left, int right, String curStr, int n)
{//遞歸終止；將一種組合添加到結果集if (left == n && right == n){res.add(curStr);return;}//若左括號使用數量小于右括號使用數量，則“剪枝”（不再進行這種錯誤模式的括號組合）if (left < right)return;//若還剩余左括號，則使用左括號if (left < n)DFS_2(res, left + 1, right, curStr + "(", n);//若還剩余右括號，則使用右括號if (right < n)DFS_2(res, left, right + 1, curStr +")", n);
}

廣搜

class Node
{String curStr;int left;   //左括號還剩幾個沒用int right; //右括號還剩幾個沒用public Node(String curStr, int left, int right){this.curStr = curStr;this.left = left;this.right = right;}
}public List<String> generateParenthesis_3(int n)
{//特判，否則n==0時下面的算法會返回""if(n == 0)return null;//結果集ArrayList<String> res = new ArrayList<String>();ArrayDeque<Node> queue = new ArrayDeque<>();//初始結點入隊queue.offer(new Node("", n, n));while (!queue.isEmpty()){//隊頭元素出隊Node curNode = queue.poll();//生成了一組有效括號if(curNode.left == 0 && curNode.right == 0)res.add(curNode.curStr);//若還剩余左括號，則使用左括號if (curNode.left > 0)queue.offer(new Node(curNode.curStr + "(", curNode.left - 1, curNode.right));//若還剩余右括號，且左括號剩余數少于右括號剩余數，則使用右括號if (curNode.right > 0 && curNode.left < curNode.right)queue.offer(new Node(curNode.curStr + ")", curNode.left, curNode.right - 1));}return res;
}