Leetcode - Hard - Swift

Reminders for problem solutions from https://leetcode.com Code snippets on Swift

2 flashcards · Computer Science · by Bohdan Orlov

  1. 301. Remove Invalid Parentheses Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results. Note: The input string may contain letters other than the parentheses ( and ). Example 1: Input: "()())()" Output: ["()()()", "(())()"] Example 2: Input: "(a)())()" Output: ["(a)()()", "(a())()"] Example 3: Input: ")(" Output: [""]

    Find left and right invalid parentheses: ) cancels left-- if any, otherwise right++ At each step generate two recursion branches: remove parenthesis if leftRem or rightRem > 0 append parenthesis to candidate string only valid parenthesis are added if char is not parenthesis then just add it to candidate string when reach end of s and leftRem == rightRem == 0 then string is valid and can be added to the result set Complexity. Time: O(2n), Space: O(n) func removeInvalidParentheses(_ s: String) ->…

  2. 304. Range Sum Query 2D - Immutable Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2). The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8. Example: Given matrix = [ [3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5] ] sumRegion(2, 1, 4, 3) -> 8 sumRegion(1, 1, 2, 2) -> 11 sumRegio…

    Image Complexity. Time: O(1), Space: O(n*m) init(_ matrix: [[Int]]) { let n = matrix.count let m = n == 0 ? 0 : matrix[0].count var dp = Array(repeating: Array(repeating: 0, count: m + 1), count: n + 1) for i in 0..<n { for j in 0..<m { dp[i + 1][j + 1] = matrix[i][j] + dp[i][j + 1] + dp[i + 1][j] - dp[i][j] } } self.dp = dp } func sumRegion(_ row1: Int, _ col1: Int, _ row2: Int, _ col2: Int) -> Int { return dp[row2 + 1][col2 + 1] - dp[row2 + 1][col1] - dp[row1][col2 + 1] + dp[row1][col1] }