LeetCode Day21 BackTracking Part 3
Flame Chan
Posted on June 29, 2024
93. Restore IP Addresses
A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.
For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.
Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order.
Example 1:
Input: s = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]
Example 2:
Input: s = "0000"
Output: ["0.0.0.0"]
Example 3:
Input: s = "101023"
Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
Constraints:
1 <= s.length <= 20
s consists of digits only.
Original Page
/**0 0,1,2
12 size
start = 3, i= 1
1,1,2, 2, 2,2...
1st element = 2;
the number of left element is : size-(start+i)
if count*3 < size-(start+1) continue;
*/
public List<String> restoreIpAddresses(String s) {
List<String> list = new ArrayList<>();
backTracking(list, new StringBuilder(), new StringBuilder(s), 0, 1);
return list;
}
public void backTracking(List<String> list, StringBuilder result, StringBuilder str, int start,int count){
if(count > 4){
list.add(result.toString());
return;
}
int size = str.length();
for(int i=1; i<=3 && start+i<=size; i++){
// pruning preocess, cut invalid size down before the recursion process
if(size-start-i > (4-count)*3){
continue;
}
String cur = str.substring(start, start+i);
boolean sign = false;
// if this number is valid or not
if(isValid(cur)){
if(count!=1){
result.append(".");
sign = true;
}
result.append(cur);
}else{
continue;
}
backTracking(list, result, str, start+i, count+1);
if(sign){
result.setLength(result.length()-cur.length()-1);
} else{
result.setLength(result.length()-cur.length());
}
}
}
public boolean isValid(String s){
int size = s.length();
// valid length
if(size<1 || size>3 ){
return false;
}
// cannot have leading zeros
if(size > 1 && s.charAt(0) == '0' ){
return false;
}
// number from 0 to 255
int num = Integer.valueOf(s);
if(num > 255){
return false;
}
return true;
}
90. Subsets II
Given an integer array nums that may contain duplicates, return all possible
subsets
(the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Example 2:
Input: nums = [0]
Output: [[],[0]]
Constraints:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
List<Integer> subset = new LinkedList<>();
list.add(new ArrayList<>());
Arrays.sort(nums);
backTracking(list, subset, nums, 0);
return list;
}
public void backTracking (List<List<Integer>> list, List<Integer> subset, int[] nums, int start){
if(start == nums.length){
// list.add(new ArrayList<>(subset));
return;
}
for(int i=start; i<nums.length; i++){
if(i!=start && nums[i] == nums[i-1]){
continue;
}
subset.add(nums[i]);
list.add(new ArrayList<>(subset));
backTracking(list, subset, nums, i+1);
subset.remove(subset.size()-1);
}
}
Posted on June 29, 2024
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.