A parentheses string is valid if and only if: It is the empty string, It can be written as AB (A concatenated with B), where A and B are valid strings, or It can be written as (A), where A is a valid string. You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string. ...
Given the root of a binary tree, return all root-to-leaf paths in any order. A leaf is a node with no children. Example 1: Input: root = [1,2,3,null,5] Output: ["1->2->5","1->3"] Example 2: Input: root = [1] Output: ["1"] Constraints: The number of nodes in the tree is in the range [1, 100]. -100 <= Node.val <= 100 Solution /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List<String> binaryTreePaths(TreeNode root) { List<String> res = new ArrayList<>(); dfs(root, res, ""); return res; } void dfs(TreeNode node, List<String> res, String s) { if (node == null) { return; } if (s.length() == 0) { s += "" + node.val; } else { s += "->" + node.val; } if (node.left == null && node.right == null) { res.add(s); return; } dfs(node.left, res, s); dfs(node.right, res, s); } }
Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order. Example 1: Input: nums = [1,1,2] Output: [[1,1,2], [1,2,1], [2,1,1]] Example 2: Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] Constraints: 1 <= nums.length <= 8 -10 <= nums[i] <= 10 Solution class Solution { public List<List<Integer>> permuteUnique(int[] nums) { List<List<Integer>> res = new ArrayList<>(); permuteAt(0, nums, res); return res; } void permuteAt(int i, int[] nums, List<List<Integer>> res) { if (i == nums.length) { res.add(toList(nums)); return; } Set<Integer> seen = new HashSet<>(); for (int j = i; j < nums.length; j++) { if (seen.add(nums[j])) { swap(i, j, nums); permuteAt(i + 1, nums, res); swap(i, j, nums); } } } void swap(int i, int j, int[] arr) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } List<Integer> toList(int[] values) { List<Integer> res = new ArrayList<>(values.length); for (int val : values) { res.add(val); } return res; } }
Given two strings s and t, return true if they are both one edit distance apart, otherwise return false. A string s is said to be one distance apart from a string t if you can: Insert exactly one character into s to get t. Delete exactly one character from s to get t. Replace exactly one character of s with a different character to get t. Example 1: Input: s = "ab", t = "acb" Output: true Explanation: We can insert 'c' into s to get t. Example 2: Input: s = "", t = "" Output: false Explanation: We cannot get t from s by only one step. Example 3: Input: s = "a", t = "" Output: true Example 4: Input: s = "", t = "A" Output: true Constraints: ...
Given a string queryIP, return “IPv4” if IP is a valid IPv4 address, “IPv6” if IP is a valid IPv6 address or “Neither” if IP is not a correct IP of any type. A valid IPv4 address is an IP in the form “x1.x2.x3.x4” where 0 <= xi <= 255 and xi cannot contain leading zeros. For example, “192.168.1.1” and “192.168.1.0” are valid IPv4 addresses but “192.168.01.1”, while “192.168.1.00” and “192.168@1.1” are invalid IPv4 addresses. ...
You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. Each list of intervals is pairwise disjoint and in sorted order. Return the intersection of these two interval lists. A closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b. The intersection of two closed intervals is a set of real numbers that are either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3]. ...
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers. Given a string s, return true if it is a palindrome, or false otherwise. Example 1: Input: s = "A man, a plan, a canal: Panama" Output: true Explanation: "amanaplanacanalpanama" is a palindrome. Example 2: Input: s = "race a car" Output: false Explanation: "raceacar" is not a palindrome. Example 3: Input: s = " " Output: true Explanation: s is an empty string "" after removing non-alphanumeric characters. Since an empty string reads the same forward and backward, it is a palindrome. Constraints: ...
Given the root of a binary search tree, return a balanced binary search tree with the same node values. If there is more than one answer, return any of them. A binary search tree is balanced if the depth of the two subtrees of every node never differs by more than 1. Example 1: Input: root = [1,null,2,null,3,null,4,null,null] Output: [2,1,3,null,null,null,4] Explanation: This is not the only correct answer, [3,1,4,null,2] is also correct. ...
Given a string num that contains only digits and an integer target, return all possibilities to insert the binary operators ‘+’, ‘-’, and/or ‘*’ between the digits of num so that the resultant expression evaluates to the target value. Note that operands in the returned expressions should not contain leading zeros. Example 1: Input: num = "123", target = 6 Output: ["1*2*3","1+2+3"] Explanation: Both "1*2*3" and "1+2+3" evaluate to 6. Example 2: Input: num = "232", target = 8 Output: ["2*3+2","2+3*2"] Explanation: Both "2*3+2" and "2+3*2" evaluate to 8. Example 3: Input: num = "105", target = 5 Output: ["1*0+5","10-5"] Explanation: Both "1*0+5" and "10-5" evaluate to 5. Note that "1-05" is not a valid expression because the 5 has a leading zero. Example 4: Input: num = "00", target = 0 Output: ["0*0","0+0","0-0"] Explanation: "0*0", "0+0", and "0-0" all evaluate to 0. Note that "00" is not a valid expression because the 0 has a leading zero. Example 5: Input: num = "3456237490", target = 9191 Output: [] Explanation: There are no expressions that can be created from "3456237490" to evaluate to 9191. Constraints: ...
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively. Merge nums1 and nums2 into a single array sorted in non-decreasing order. The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n. ...