Leetcode

244. Shortest Word Distance II Design a data structure that will be initialized with a string array, and then it should answer queries of the shortest distance between two different strings from the array. Implement the WordDistance class: WordDistance(String[] wordsDict) initializes the object with the strings array wordsDict. int shortest(String word1, String word2) returns the shortest distance between word1 and word2 in the array wordsDict. Example 1: Input ["WordDistance", "shortest", "shortest"] [[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]] Output [null, 3, 1] Explanation WordDistance wordDistance = new WordDistance(["practice", "makes", "perfect", "coding", "makes"]); wordDistance.shortest("coding", "practice"); // return 3 wordDistance.shortest("makes", "coding"); // return 1 Constraints: ...

245. Shortest Word Distance III Given an array of strings wordsDict and two strings that already exist in the array word1 and word2, return the shortest distance between these two words in the list. Note that word1 and word2 may be the same. It is guaranteed that they represent two individual words in the list. Example 1: Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding" Output: 1 Example 2: Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "makes" Output: 3 Constraints: ...

191. Number of 1 Bits Write a function that takes an unsigned integer and returns the number of ‘1’ bits it has (also known as the Hamming weight). Note: Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned. In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 3, the input represents the signed integer. -3. Example 1: Input: n = 00000000000000000000000000001011 Output: 3 Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits. Example 2: Input: n = 00000000000000000000000010000000 Output: 1 Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit. Example 3: Input: n = 11111111111111111111111111111101 Output: 31 Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits. Constraints: ...

231. Power of Two Given an integer n, return true if it is a power of two. Otherwise, return false. An integer n is a power of two, if there exists an integer x such that n == 2x. Example 1: Input: n = 1 Output: true Explanation: 20 = 1 Example 2: Input: n = 16 Output: true Explanation: 24 = 16 Example 3: Input: n = 3 Output: false Example 4: Input: n = 4 Output: true Example 5: Input: n = 5 Output: false Constraints: ...

835. Image Overlap You are given two images img1 and img2 both of size n x n, represented as binary, square matrices of the same size. (A binary matrix has only 0s and 1s as values.) We translate one image however we choose (sliding it left, right, up, or down any number of units), and place it on top of the other image. After, the overlap of this translation is the number of positions that have a 1 in both images. ...

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); } } }

832. Flipping an Image Given an n x n binary matrix image, flip the image horizontally, then invert it, and return the resulting image. To flip an image horizontally means that each row of the image is reversed. For example, flipping [1,1,0] horizontally results in [0,1,1]. To invert an image means that each 0 is replaced by 1, and each 1 is replaced by 0. For example, inverting [0,1,1] results in [1,0,0]. Example 1: Input: image = [[1,1,0],[1,0,1],[0,0,0]] Output: [[1,0,0],[0,1,0],[1,1,1]] Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]]. Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]] Example 2: Input: image = [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]] Output: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]] Explanation: First reverse each row: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]]. Then invert the image: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]] Constraints: ...

833. Find And Replace in String To some string s, we will perform some replacement operations that replace groups of letters with new ones (not necessarily the same size). Each replacement operation has 3 parameters: a starting index i, a source word x and a target word y. The rule is that if x starts at position i in the original string S, then we will replace that occurrence of x with y. If not, we do nothing. ...

1441. Build an Array With Stack Operations Given an array target and an integer n. In each iteration, you will read a number from list = {1,2,3…, n}. Build the target array using the following operations: Push: Read a new element from the beginning list, and push it in the array. Pop: delete the last element of the array. If the target array is already built, stop reading more elements. Return the operations to build the target array. You are guaranteed that the answer is unique. ...