DSA

Problem Statement: Wildcard Matching Given two strings s and p, return true if s matches p (with wildcard characters), and false otherwise. The string p can contain the following wildcard characters: Example: Example 1: Input: s = “aa”, p = “a*”Output: trueExplanation: “a*” matches “aa” because ‘*’ can match the second ‘a’. Example 2: Input: s = “mississippi”, p = “mis*is*p*.”Output: false Example 3: Input: s = “adceb”, p = “*a*b”Output: trueExplanation: The pattern “*a*b” matches the string “adceb”. Approach: The problem can be solved using Dynamic Programming (DP). The idea is to use a 2D DP table where dp[i][j] represents whether the substring s[0..i-1] matches the pattern p[0..j-1]. Steps: Dynamic Programming Solution: Python Code: def isMatch(s: str, p: str) -> bool: # dp[i][j] will be True if s[0…i-1] matches p[0…j-1] dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)] # Initial condition: empty string matches empty pattern dp[0][0] = True # If the pattern starts with ‘*’ it can match the empty string for j in range(1, len(p) + 1): if p[j – 1] == ‘*’: dp[0][j] = dp[0][j – 1] # Fill the dp table for i in range(1, len(s) + 1): for j in range(1, len(p) + 1): if p[j – 1] == s[i – 1] or p[j – 1] == ‘?’: dp[i][j] = dp[i – 1][j – 1] elif p[j – 1] == ‘*’: dp[i][j] = dp[i – 1][j] or dp[i][j – 1] # The bottom-right corner will contain the answer return dp[len(s)][len(p)] Explanation of the Code: Time and Space Complexity: Example Walkthrough: Example 1: Input: s = “aa”, p = “a*” The final result is True, as dp[2][2] = True. Example 2: Input: s = “mississippi”, p = “mis*is*p*.” Conclusion: The Wildcard Matching problem is efficiently solved using Dynamic Programming. By filling a DP table and considering all possible ways a wildcard can match a sequence of characters, we can determine if the string matches the pattern with wildcards * and ?. The time complexity of O(m * n) is suitable for handling reasonably large inputs, where m and n are the lengths of the string and the pattern, respectively.

Problem Statement: Multiply Strings Given two non-negative integers num1 and num2 represented as strings, return the product of num1andnum2`, also as a string. Note: Example: Example 1: Input: num1 = “2”, num2 = “3”Output: “6” Example 2: Input: num1 = “123”, num2 = “456”Output: “56088” Example 3: Input: num1 = “0”, num2 = “0”Output: “0” Approach: Multiplying large numbers represented as strings without converting them to integers can be achieved using the standard method of multiplication that we learn in elementary school: long multiplication. Here’s the step-by-step breakdown: Algorithm: Code Implementation: Python: def multiply(num1: str, num2: str) -> str: # Edge case: if either number is “0”, the result is “0” if num1 == “0” or num2 == “0”: return “0” # Initialize the result array with zeros. The maximum length of the result # can be at most len(num1) + len(num2). result = [0] * (len(num1) + len(num2)) # Reverse num1 and num2 to make the multiplication easier num1 = num1[::-1] num2 = num2[::-1] # Perform multiplication for i in range(len(num1)): for j in range(len(num2)): # Multiply digits and add to the corresponding position in the result array product = int(num1[i]) * int(num2[j]) result[i + j] += product result[i + j + 1] += result[i + j] // 10 # Carry to the next position result[i + j] %= 10 # Keep only the single digit at the current position # The result array now contains the digits of the product in reverse order. # We need to remove any leading zeros. # Convert the result to a string result = result[::-1] # Skip leading zeros result_str = ”.join(map(str, result)).lstrip(‘0’) return result_str Explanation of the Code: Time and Space Complexity: Example Walkthrough: Example 1: Input: num1 = “123”, num2 = “456” Edge Case Examples: Example 2: Input: num1 = “0”, num2 = “123” Example 3: Input: num1 = “999”, num2 = “999” Conclusion: The Multiply Strings problem is solved by simulating the long multiplication process. This method avoids the use of built-in integer multiplication and provides an efficient solution with a time complexity of O(m * n). By handling carries and constructing the result step by step, we can multiply large numbers represented as strings and return the result as a string.

Problem Statement: Count and Say The Count and Say sequence is a sequence of strings where each term is derived from the previous one by describing the frequency and value of the consecutive digits in the string. For example: Given an integer n, generate the nth term of the Count and Say sequence. Input: Output: Example: Example 1: Input: n = 1Output: “1” Example 2: Input: n = 4Output: “1211” Approach: The process to generate the nth term in the Count and Say sequence involves the following steps: Algorithm: Code Implementation: Python: def countAndSay(n: int) -> str: # The first term in the sequence is always “1” result = “1” # Build the sequence iteratively for n-1 times for _ in range(1, n): next_result = “” count = 1 # Traverse through the current result string for i in range(1, len(result)): if result[i] == result[i – 1]: # If the current character is the same as the previous one, increment the count count += 1 else: # If the current character is different, append the count and character to next_result next_result += str(count) + result[i – 1] count = 1 # Reset count for the new character # Don’t forget to append the last group of characters next_result += str(count) + result[-1] # Update result for the next iteration result = next_result return result Explanation of Code: Time and Space Complexity: Example Walkthrough: Example 1: Input: n = 1 Example 2: Input: n = 4 Example 3: Input: n = 5 Edge Cases: Conclusion: The Count and Say problem can be solved efficiently using an iterative approach where each term is built from the previous one by counting and describing consecutive digits. This approach runs in linear time relative to the size of the terms, making it efficient enough for the given constraints.

Problem Statement: Longest Valid Parentheses Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring. Definition of Valid Parentheses: Input: Output: Example: Example 1: Input: s = “(()”Output: 2Explanation: The longest valid parentheses substring is “()”. Example 2: Input: s = “)()())”Output: 4Explanation: The longest valid parentheses substring is “()()”. Example 3: Input: s = “”Output: 0Explanation: The string is empty, so there is no valid parentheses substring. Approach: To solve this problem, we need to find the longest substring of valid parentheses. There are several approaches to solving this problem efficiently: Algorithm (Using Stack): Stack Approach Explanation: Code Implementation (Using Stack): Python: def longestValidParentheses(s: str) -> int: stack = [-1] # Initialize the stack with -1 to help with length calculations max_len = 0 for i, char in enumerate(s): if char == ‘(‘: stack.append(i) # Push the index of ‘(‘ onto the stack else: stack.pop() # Pop the last element when encountering ‘)’ if not stack: stack.append(i) # Push the current index as the base for the next valid substring else: max_len = max(max_len, i – stack[-1]) # Calculate the length of valid substring return max_len Explanation of Code: Time and Space Complexity: Edge Cases: Example Walkthrough: Example 1: Input: s = “(()” Example 2: Input: s = “)()())” Alternative Approaches: However, the stack approach provides the most intuitive and space-efficient solution for this problem.

Problem Statement: Substring with Concatenation of All Words Given a string s and a list of words words, you need to find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters. Each word in the list words has the same length. The length of the concatenated substring is the sum of the lengths of all the words, and the substring must consist of exactly one occurrence of each word from the list (in any order). Input: Output: Example: Example 1: Input: s = “barfoothefoobarman”, words = [“foo”, “bar”]Output: [0, 9]Explanation: The substring starting at index 0 is “barfoo”, and the substring starting at index 9 is “foobar”. Example 2: Input: s = “wordgoodgoodgoodbestword”, words = [“word”, “good”, “best”, “good”]Output: [8]Explanation: The substring starting at index 8 is “goodbestword”. Approach: Algorithm: Code Implementation: Python: from collections import Counterdef findSubstring(s, words): if not s or not words: return [] word_len = len(words[0]) word_count = len(words) word_map = Counter(words) # Frequency map of the words in ‘words’ result = [] # Sliding window of size word_len * word_count for i in range(word_len): left = i right = i current_count = 0 window_map = Counter() # Map to track the current window while right + word_len <= len(s): word = s[right:right + word_len] right += word_len if word in word_map: window_map[word] += 1 current_count += 1 # If the word count exceeds the expected count, move left pointer while window_map[word] > word_map[word]: left_word = s[left:left + word_len] window_map[left_word] -= 1 current_count -= 1 left += word_len # If we have found all words in the window, add to the result if current_count == word_count: result.append(left) else: # Reset the window if the word is not in the words list window_map.clear() current_count = 0 left = right return result Explanation: Time and Space Complexity: Example Walkthrough: Example 1: Input: s = “barfoothefoobarman”, words = [“foo”, “bar”] Example 2: Input: s = “wordgoodgoodgoodbestword”, words = [“word”, “good”, “best”, “good”]

Problem Statement: Given a string s and a target character ch, your task is to find the index of the first occurrence of the character ch in the string s. If the character is not found, return -1. Input: Output: Example: Example 1: Input: s = “hello”, ch = ‘e’Output: 1Explanation: The first occurrence of ‘e’ is at index 1. Example 2: Input: s = “hello”, ch = ‘a’Output: -1Explanation: ‘a’ is not present in the string. Approach: To solve the problem, we can use a linear scan of the string s to look for the character ch. The first occurrence of ch in the string will be returned as the index. If no match is found, return -1. Algorithm: Code Implementation: C: #include <stdio.h>#include <string.h>int first_occurrence(char* s, char ch) { for (int i = 0; i < strlen(s); i++) { if (s[i] == ch) { return i; } } return -1;}int main() { char s[] = “hello”; char ch = ‘e’; int result = first_occurrence(s, ch); printf(“%d\n”, result); // Output: 1 return 0;} C++: #include <iostream>#include <string>using namespace std;int first_occurrence(string s, char ch) { for (int i = 0; i < s.length(); i++) { if (s[i] == ch) { return i; } } return -1;}int main() { string s = “hello”; char ch = ‘e’; cout << first_occurrence(s, ch) << endl; // Output: 1 return 0;} Java: public class Main { public static int firstOccurrence(String s, char ch) { for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == ch) { return i; } } return -1; } public static void main(String[] args) { String s = “hello”; char ch = ‘e’; System.out.println(firstOccurrence(s, ch)); // Output: 1 }} Python: def first_occurrence(s, ch): for i in range(len(s)): if s[i] == ch: return i return -1s = “hello”ch = ‘e’print(first_occurrence(s, ch)) # Output: 1 C#: using System;class Program { static int FirstOccurrence(string s, char ch) { for (int i = 0; i < s.Length; i++) { if (s[i] == ch) { return i; } } return -1; } static void Main() { string s = “hello”; char ch = ‘e’; Console.WriteLine(FirstOccurrence(s, ch)); // Output: 1 }} JavaScript: function firstOccurrence(s, ch) { for (let i = 0; i < s.length; i++) { if (s[i] === ch) { return i; } } return -1;}let s = “hello”;let ch = ‘e’;console.log(firstOccurrence(s, ch)); // Output: 1 Time Complexity: Space Complexity: Edge Cases:

Min cost path by means of memoizing DP: We utilize a 2D array for memorizing since the recursive solution changes two parameters.To signify that no values are computed initially, we start the 2D array as -1.First we check in the memo table in the recursion. Should we detect value as -1, we only call recursively. In this sense, we avoid recommendations of the same sub-problems. C++ Java Python JavaScript Time Complexity: O(M * N)Auxiliary Space: O(M * N)

Write a function returning cost of minimum cost path to reach (M, N) from (0, 0) considering a cost matrix cost[][ and a position (M, N) in cost[][]. Every matrix cell stands for a cost to be crossed through. Including both source and destination, a path’s total cost to reach (M, N) is the sum of all the expenses on that path. From a given cell, i.e., from a given i, j, cells (i+1, j), and (i, j+1) can be navigated only down, right and diagonally lower cells. Note: You might suppose that every expense is a positive integer. Input The path with minimum cost is highlighted in the following figure. The path is (0, 0) –> (0, 1) –> (1, 2) –> (2, 2). The cost of the path is 8 (1 + 2 + 2 + 3).   Output Table of Content Recursion allows a minimum cost path. Use the below concept to address the issue: The optimal substructure property of this issue exists. One of the three cells—either (m-1, n-1) or (m-1, n) or (m, n-1)—must be the route of reach (m, n). Minimum cost to reach (m, n) can thus be expressed as “minimum of the 3 cells plus cost[m][n]”.min (minCost(m-1, n-1), minCost(m-1, n), minCost(m, n-1)) + cost[m][n] minCost(m, n) C++ C Java Python C# JavaScript Output 8 Time Complexity: O((M * N)3)Auxiliary Space: O(M + N), for recursive stack space

Using Space Optimised DP – O(m*n) Time and O(n) Space We can maximize space by utilizing a single 1D array dp of size c (number of columns), since every dp[i][j] depends just on the left cell of the current row and the previous row. C++ Java Python C# JavaScript

Using Bottom-Up DP (Tabulation) – O(m*n) Time and O(m*n) Space Here the challenge is to determine the count of distinct paths in a grid including obstacles. The state dp[i][j] will show the count of different paths to go to the cell (i, j). Relation in Dynamic Programming: C++ Java Python C# Output 2