Hi there 👋

The problem Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Note that the same word in the dictionary may be reused multiple times in the segmentation. Examples Input: s = "leetcode", wordDict = ["leet","code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code". Input: s = "applepenapple", wordDict = ["apple","pen"] Output: true Explanation: Return true because "applepenapple" can be segmented as "apple pen apple". Note that you are allowed to reuse a dictionary word. Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] Output: false Constraints 1 <= s.length <= 300 1 <= wordDict.length <= 1000 1 <= wordDict[i].length <= 20 s and wordDict[i] consist of only lowercase English letters. All the strings of wordDict are unique. Recursion solution func wordBreak(_ s: String, _ wordDict: [String]) -> Bool { let sCount = s.count let sArray = Array(s) func dfs(_ i: Int) -> Bool { if i == sCount { return true } for w in wordDict { let wCount = w.count if ((i + wCount) <= sCount && String(sArray[i ..< i + wCount]) == w ) { if dfs(i + wCount) { return true } } } return false } return dfs(0) } Explanation There are multiple ways to solve this problem. For example, we can check every character in input s and compare it with characters in wordDict, but this approach is inefficient from a time complexity perspective. Instead: ...

The problem Given an integer array nums, find a subarray that has the largest product and return the product. A subarray is a contiguous, non-empty sequence of elements within an array. The test cases are generated so that the answer will fit in a 32-bit integer. Examples Input: nums = [2,3,-2,4] Output: 6 Explanation: [2,3] has the largest product 6. Input: nums = [-2,0,-1] Output: 0 Explanation: The result cannot be 2 because [-2,-1] is not a subarray. Constraints 1 <= nums.length <= 2 * 10⁴ -10 <= nums[i] <= 10 The product of any subarray of nums is guaranteed to fit in a 32-bit integer. Brute force solution func maxProduct(_ nums: [Int]) -> Int { var res = nums[0] let n = nums.count for i in 0 ..< n { var curr = nums[i] res = max(res, curr) for j in i + 1 ..< n { curr *= nums[j] res = max(res, curr) } } return res } Explanation The brute-force way to solve this problem is to try every single subarray and calculate the product for each. This is not very efficient, and the time complexity will be O(n²). We can solve this problem in a more optimal way. ...

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. ...