LeetCode

The problem You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. You may assume that you have an infinite number of each kind of coin. Examples Input: coins = [1,2,5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1 Input: coins = [2], amount = 3 Output: -1 Input: coins = [1], amount = 0 Output: 0 Constraints 1 <= coins.length <= 12 1 <= coins[i] <= 2³¹ - 1 0 <= amount <= 10⁴ Dynamic programming top-down solution func coinChange(_ coins: [Int], _ amount: Int) -> Int { var memo: [Int: Int] = [:] let int1e9 = Int(1e9) func dfs(_ amount: Int) -> Int { if amount == 0 { return 0 } if let val = memo[amount] { return val } var res = int1e9 for coin in coins { if amount - coin >= 0 { res = min(res, 1 + dfs(amount - coin)) } } memo[amount] = res return res } let minCoins = dfs(amount) if minCoins >= int1e9 { return -1 } else { return minCoins } } Explanation One of the ways that we can solve this problem is by using a depth-first search algorithm with memoization to optimize the overall time complexity. ...

The Problem You have intercepted a secret message encoded as a string of numbers. The message is decoded via the following mapping: "1" → 'A' "2" → 'B' … "25" → 'Y' "26" → 'Z' However, while decoding the message, you realize that there are many different ways to decode it because some codes are contained within others (e.g., "2" and "5" vs. "25"). For example, "11106" can be decoded into: ...

The Problem Given a string s, return the number of palindromic substrings in it. A string is a palindrome when it reads the same backward as forward. A substring is a contiguous sequence of characters within the string. Examples Input: s = "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c". Input: s = "aaa" Output: 6 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa". Constraints 1 <= s.length <= 1000 s consists of lowercase English letters. Brute Force Solution func countSubstrings(_ s: String) -> Int { let n = s.count let sArray = Array(s) var res = 0 for i in 0 ..< n { for j in i ..< n { var l = i var r = j while l < r && sArray[l] == sArray[r] { l += 1 r -= 1 } res += (l >= r) ? 1 : 0 } } return res } Explanation We can solve this problem by understanding how a brute-force approach works and then optimizing it. ...

The Problem Given a string s, return the longest palindromic substring in s. A string is palindromic if it reads the same forward and backward. Examples Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer. Input: s = "cbbd" Output: "bb" Constraints 1 <= s.length <= 1000 s consists of only digits and English letters. Brute Force Solution func longestPalindrome(_ s: String) -> String { let sArray = Array(s) var res = "" var resLen = 0 let n = s.count for i in 0 ..< n { for j in i ..< n { var l = i var r = j while l < r && sArray[l] == sArray[r] { l += 1 r -= 1 } if l >= r && resLen < (j - i + 1) { res = String(sArray[i ..< j + 1]) resLen = j - i + 1 } } } return res } Explanation In the first example, we are given the input "babad". Let’s visualize it and try to find the longest palindromic substring. ...

The problem You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses in this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses are broken into on the same night. ...