Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once. Example 1: Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" Output: true ...
You are given an integer array cards of length 4. You have four cards, each containing a number in the range [1, 9]. You should arrange the numbers on these cards in a mathematical expression using the operators [’+’, ‘-’, ‘*’, ‘/’] and the parentheses ‘(’ and ‘)’ to get the value 24. You are restricted with the following rules: The division operator ‘/’ represents real division, not integer division. For example, 4 / (1 - 2 / 3) = 4 / (1 / 3) = 12. Every operation done is between two numbers. In particular, we cannot use ‘-’ as a unary operator. For example, if cards = [1, 1, 1, 1], the expression “-1 - 1 - 1 - 1” is not allowed. You cannot concatenate numbers together For example, if cards = [1, 2, 1, 2], the expression “12 + 12” is not valid. Return true if you can get such expression that evaluates to 24, and false otherwise. ...
Given a pattern and a string s, return true if s matches the pattern. A string s matches a pattern if there is some bijective mapping of single characters to strings such that if each character in pattern is replaced by the string it maps to, then the resulting string is s. A bijective mapping means that no two characters map to the same string, and no character maps to two different strings. ...
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 controlling a robot that is located somewhere in a room. The room is modeled as an m x n binary grid where 0 represents a wall and 1 represents an empty slot. The robot starts at an unknown location in the root that is guaranteed to be empty, and you do not have access to the grid, but you can move the robot using the given API Robot. ...
31. Next Permutation Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order). The replacement must be in place and use only constant extra memory. Example 1: Input: nums = [1,2,3] Output: [1,3,2] Example 2: Input: nums = [3,2,1] Output: [1,2,3] Example 3: Input: nums = [1,1,5] Output: [1,5,1] Example 4: Input: nums = [1] Output: [1] Constraints: ...
131. Palindrome Partitioning Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. A palindrome string is a string that reads the same backward as forward. Example 1: Input: s = "aab" Output: [["a","a","b"],["aa","b"]] Example 2: Input: s = "a" Output: [["a"]] Constraints: 1 <= s.length <= 16 s contains only lowercase English letters. Solution class Solution { public List<List<String>> partition(String s) { List<List<String>> res = new ArrayList<>(); List<String> current = new ArrayList<>(); back(0, s.toCharArray(), current, res); return res; } void back(int index, char[] s, List<String> current, List<List<String>> res) { if (index == s.length) { res.add(new ArrayList<>(current)); return; } for (int i = index + 1; i <= s.length; i++) { if (isPalindrom(s, index, i)) { current.add(new String(Arrays.copyOfRange(s, index, i))); back(i, s, current, res); current.remove(current.size() - 1); } } } boolean isPalindrom(char[] s, int i, int j) { if (i == j) return false; if (j - i == 1) return true; while (i < j) { if (s[i++] != s[--j]) { return false; } } return true; } }
301. Remove Invalid Parentheses Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid. Return all the possible results. You may return the answer in any order. Example 1: Input: s = "()())()" Output: ["(())()","()()()"] Example 2: Input: s = "(a)())()" Output: ["(a())()","(a)()()"] Example 3: Input: s = ")(" Output: [""] Constraints: 1 <= s.length <= 25 s consists of lowercase English letters and parentheses ‘(’ and ‘)’. There will be at most 20 parentheses in s. Solution class Solution { public List<String> removeInvalidParentheses(String s) { TreeMap<Integer, Set<String>> res = new TreeMap<>(); back(0, s, "", res, 0, 0); return new ArrayList<>(res.firstEntry().getValue()); } void back(int index, String s, String current, Map<Integer, Set<String>> res, int open, int closed) { if (index == s.length()) { if (open == closed) { int removed = s.length() - current.length(); Set<String> values = res.getOrDefault(removed, new TreeSet<>()); values.add(current); res.put(removed, values); } return; } if (closed > open) return; char c = s.charAt(index); if (c == '(' || c == ')') { back(index + 1, s, current + c, res, (c == '(') ? open + 1: open, (c == ')') ? closed + 1: closed); back(index + 1, s, current, res, open, closed); } else { back(index + 1, s, current + c, res, open, closed); } } } Solution 2021-10-15 class Solution { public List<String> removeInvalidParentheses(String s) { int opened = 0; int closed = 0; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (c == '(') { opened++; } else if (c == ')') { if (opened > 0) { opened--; } else { closed++; } } } List<String> res = new ArrayList<>(); StringBuilder sb = new StringBuilder(); backtrack(0, s, res, opened, closed, 0, sb); return res; } void backtrack(int pos, String s, List<String> res, int opened, int closed, int currOpened, StringBuilder sb) { if (opened < 0 || closed < 0 || currOpened < 0) return; if (pos == s.length()) { if (opened == 0 && closed == 0 && currOpened == 0) { if (!res.contains(sb.toString())) { res.add(sb.toString()); } } return; } if (opened < 0 || closed < 0 || currOpened < 0) return; // "()())()" // 0123456 // (())() 0 0 0 pos = 2 char c = s.charAt(pos); if (c != '(' && c != ')') { sb.append(c); backtrack(pos + 1, s, res, opened, closed, currOpened, sb); } if (c == '(') { // remove backtrack(pos + 1, s, res, opened - 1, closed, currOpened, sb); //skip sb.append(c); backtrack(pos + 1, s, res, opened, closed, currOpened + 1, sb); } else if (c == ')') { // remove backtrack(pos + 1, s, res, opened, closed - 1, currOpened, sb); //skip sb.append(c); backtrack(pos + 1, s, res, opened, closed, currOpened - 1, sb); } sb.deleteCharAt(sb.length() - 1); } } Solution 2021-10-23 class Solution { public List<String> removeInvalidParentheses(String s) { int opened = 0; int closed = 0; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (c == '(') { opened++; } else if (c == ')') { if (opened > 0) { opened--; } else { closed++; } } } List<String> res = new ArrayList<>(); StringBuilder sb = new StringBuilder(); back(s, 0, opened, closed, sb, res, 0, 0); return res; } void back(String s, int index, int opened, int closed, StringBuilder sb, List<String> res, int currOpen, int currClose) { if (opened < 0 || closed < 0) return; if (currClose > currOpen) return; if (index == s.length()) { if (closed == 0 && opened == 0) { String str = sb.toString(); if (!res.contains(str)) { res.add(str); } } return; } char c = s.charAt(index); if (c == '(') { back(s, index + 1, opened - 1, closed, sb, res, currOpen, currClose); } else if (c == ')') { back(s, index + 1, opened, closed - 1, sb, res, currOpen, currClose); } sb.append(c); back(s, index + 1, opened, closed, sb, res, c == '('? currOpen + 1: currOpen, c == ')'? currClose + 1: currClose); sb.deleteCharAt(sb.length() - 1); } } Solution 2022-01-24 class Solution { public List<String> removeInvalidParentheses(String s) { StringBuilder sb = new StringBuilder(); Set<String> res = new HashSet<>(); int open = 0; for (char c: s.toCharArray()) { if (c == '(') { open++; } else if (c == ')') { if (open > 0) { open--; } } } int close = 0; for (int i = s.length() - 1; i >= 0; i--) { char c = s.charAt(i); if (c == '(') { if (close > 0) { close--; } } else if (c == ')') { close++; } } // System.out.println(open + " " + close); backtrack(0, s, 0, open, close, sb, res); return new ArrayList<>(res); } void backtrack(int index, String s, int openClosed, int open, int close, StringBuilder sb, Set<String> res) { if (open < 0 || close < 0) return; if (index == s.length()) { if (open == 0 && close == 0) { res.add(sb.toString()); } return; } char c = s.charAt(index); if (c == '(') { sb.append(c); // add open backtrack(index + 1, s, openClosed + 1, open, close, sb, res); sb.deleteCharAt(sb.length() - 1); // skip open backtrack(index + 1, s, openClosed, open - 1, close, sb, res); } else if (c == ')') { if (openClosed > 0) { sb.append(c); // add close backtrack(index + 1, s, openClosed - 1, open, close, sb, res); sb.deleteCharAt(sb.length() - 1); } // skip close backtrack(index + 1, s, openClosed, open, close - 1, sb, res); } else { sb.append(c); backtrack(index + 1, s, openClosed, open, close, sb, res); sb.deleteCharAt(sb.length() - 1); } } }
77. Combinations Given two integers n and k, return all possible combinations of k numbers out of the range [1, n]. You may return the answer in any order. Example 1: Input: n = 4, k = 2 Output: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] Example 2: Input: n = 1, k = 1 Output: [[1]] Constraints: 1 <= n <= 20 1 <= k <= n Solution class Solution { public List<List<Integer>> combine(int n, int k) { List<List<Integer>> res = new ArrayList<>(); List<Integer> current = new ArrayList<>(); back(1, n, k, current, res); return res; } void back(int value, int n, int k, List<Integer> current, List<List<Integer>> res) { if (current.size() == k) { res.add(new ArrayList<>(current)); return; } for (int i = value; i <= n; i++) { current.add(i); back(i + 1, n, k, current, res); current.remove(current.size() - 1); } } }
17. Letter Combinations of a Phone Number Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order. A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters. Example 1: Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"] Example 2: Input: digits = "" Output: [] Example 3: Input: digits = "2" Output: ["a","b","c"] ...