SkylineWebZ

Problem Statement: Given a string s and a pattern p, implement a regular expression matching algorithm to determine if s matches p. The pattern may include the characters: The matching should cover the entire string (not just a substring). Example: Input: Output: Explanation: The pattern a* matches zero or more a‘s. In this case, the pattern a* matches the string “aa”. Input: Output: Explanation: The pattern doesn’t match the string. Approach: This problem can be efficiently solved using Dynamic Programming (DP). The idea is to build a 2D DP table where each entry dp[i][j] represents whether the substring s[0..i-1] matches the pattern p[0..j-1]. Time Complexity: Space Complexity: Algorithm: Code Implementation: 1. C #include <stdio.h>#include <stdbool.h>#include <string.h>bool isMatch(char* s, char* p) { int m = strlen(s), n = strlen(p); bool dp[m+1][n+1]; dp[0][0] = true; for (int j = 1; j <= n; j++) { dp[0][j] = (p[j-1] == ‘*’ && dp[0][j-2]); } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (p[j-1] == s[i-1] || p[j-1] == ‘.’) { dp[i][j] = dp[i-1][j-1]; } else if (p[j-1] == ‘*’) { dp[i][j] = dp[i][j-2] || ((s[i-1] == p[j-2] || p[j-2] == ‘.’) && dp[i-1][j]); } else { dp[i][j] = false; } } } return dp[m][n];}int main() { char s[] = “aa”; char p[] = “a*”; printf(“%s\n”, isMatch(s, p) ? “True” : “False”); return 0;} 2. C++ #include <iostream>#include <vector>#include <cstring>using namespace std;bool isMatch(string s, string p) { int m = s.size(), n = p.size(); vector<vector<bool>> dp(m+1, vector<bool>(n+1, false)); dp[0][0] = true; for (int j = 1; j <= n; j++) { if (p[j-1] == ‘*’) { dp[0][j] = dp[0][j-2]; } } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (p[j-1] == s[i-1] || p[j-1] == ‘.’) { dp[i][j] = dp[i-1][j-1]; } else if (p[j-1] == ‘*’) { dp[i][j] = dp[i][j-2] || (dp[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == ‘.’)); } } } return dp[m][n];}int main() { string s = “aa”; string p = “a*”; cout << (isMatch(s, p) ? “True” : “False”) << endl; return 0;} 3. Java public class Solution { public boolean isMatch(String s, String p) { int m = s.length(), n = p.length(); boolean[][] dp = new boolean[m + 1][n + 1]; dp[0][0] = true; for (int j = 1; j <= n; j++) { if (p.charAt(j – 1) == ‘*’) { dp[0][j] = dp[0][j – 2]; } } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (p.charAt(j – 1) == s.charAt(i – 1) || p.charAt(j – 1) == ‘.’) { dp[i][j] = dp[i – 1][j – 1]; } else if (p.charAt(j – 1) == ‘*’) { dp[i][j] = dp[i][j – 2] || (dp[i – 1][j] && (s.charAt(i – 1) == p.charAt(j – 2) || p.charAt(j – 2) == ‘.’)); } } } return dp[m][n]; } public static void main(String[] args) { Solution solution = new Solution(); System.out.println(solution.isMatch(“aa”, “a*”)); // Output: true }} 4. Python def isMatch(s: str, p: str) -> bool: m, n = len(s), len(p) dp = [[False] * (n + 1) for _ in range(m + 1)] dp[0][0] = True for j in range(1, n + 1): if p[j – 1] == ‘*’: dp[0][j] = dp[0][j – 2] for i in range(1, m + 1): for j in range(1, n + 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][j – 2] or (dp[i – 1][j] and (s[i – 1] == p[j – 2] or p[j – 2] == ‘.’)) return dp[m][n]# Test the functionprint(isMatch(“aa”, “a*”)) # Output: True 5. C# using System;public class Solution { public bool IsMatch(string s, string p) { int m = s.Length, n = p.Length; bool[,] dp = new bool[m + 1, n + 1]; dp[0, 0] = true; for (int j = 1; j <= n; j++) { if (p[j – 1] == ‘*’) { dp[0, j] = dp[0, j – 2]; } } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (p[j – 1] == s[i – 1] || p[j – 1] == ‘.’) { dp[i, j] = dp[i – 1, j – 1]; } else if (p[j – 1] == ‘*’) { dp[i, j] = dp[i, j – 2] || (dp[i – 1, j] && (s[i – 1] == p[j – 2] || p[j – 2] == ‘.’)); } } } return dp[m, n]; } public static void Main() { Solution solution = new Solution(); Console.WriteLine(solution.IsMatch(“aa”, “a*”)); // Output: True }} 6. JavaScript var isMatch = function(s, p) { const m = s.length, n = p.length; const dp = Array.from(Array(m + 1), () => Array(n + 1).fill(false)); dp[0][0] = true; for (let j = 1; j <= n; j++) { if (p[j – 1] === ‘*’) { dp[0][j] = dp[0][j – 2]; } } for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { if (p[j – 1] === s[i – 1] || p[j – 1] === ‘.’) { dp[i][j] = dp[i – 1][j – 1]; } else if (p[j – 1] === ‘*’) { dp[i][j] = dp[i][j – 2] || (dp[i – 1][j] && (s[i – 1] === p[j – 2] || p[j – 2] === ‘.’)); } } } return dp[m][n];};// Test the functionconsole.log(isMatch(“aa”, “a*”)); // Output: true Conclusion: This algorithm efficiently solves the problem of regular expression matching using Dynamic Programming (DP). The DP approach ensures that we check all possible ways a substring of s can match the pattern p. The time and space complexities are O(m * n), where m and n are the lengths of the string and the pattern, respectively.

Problem Statement: Given a string s, find the longest palindromic substring in s. A palindrome is a string that reads the same forwards and backwards. You need to return the longest palindromic substring. Example: Example 1: Input:s = “babad” Output:”bab”(Note: “aba” is also a valid answer.) Example 2: Input:s = “cbbd” Output:”bb” Approach: We can solve this problem using Dynamic Programming (DP). The idea is to build a 2D table dp, where each entry dp[i][j] represents whether the substring s[i…j] is a palindrome. If dp[i][j] is True, it means that the substring s[i…j] is a palindrome. The transitions are as follows: Time Complexity: Algorithm: Code Implementation in Different Languages: 1. C: #include <stdio.h>#include <string.h>char* longestPalindrome(char* s) { int n = strlen(s); if (n == 0) return “”; int dp[n][n]; memset(dp, 0, sizeof(dp)); int start = 0, maxLength = 1; for (int i = 0; i < n; i++) { dp[i][i] = 1; } for (int length = 2; length <= n; length++) { for (int i = 0; i < n – length + 1; i++) { int j = i + length – 1; if (s[i] == s[j] && (length == 2 || dp[i + 1][j – 1])) { dp[i][j] = 1; if (length > maxLength) { start = i; maxLength = length; } } } } char* result = (char*)malloc((maxLength + 1) * sizeof(char)); strncpy(result, s + start, maxLength); result[maxLength] = ‘\0’; return result;}int main() { char s[] = “babad”; printf(“Longest Palindromic Substring: %s\n”, longestPalindrome(s)); return 0;} 2. C++: #include <iostream>#include <vector>#include <cstring>using namespace std;string longestPalindrome(string s) { int n = s.length(); if (n == 0) return “”; vector<vector<bool>> dp(n, vector<bool>(n, false)); int start = 0, maxLength = 1; for (int i = 0; i < n; i++) { dp[i][i] = true; } for (int length = 2; length <= n; length++) { for (int i = 0; i < n – length + 1; i++) { int j = i + length – 1; if (s[i] == s[j] && (length == 2 || dp[i + 1][j – 1])) { dp[i][j] = true; if (length > maxLength) { start = i; maxLength = length; } } } } return s.substr(start, maxLength);}int main() { string s = “babad”; cout << “Longest Palindromic Substring: ” << longestPalindrome(s) << endl; return 0;} 3. Java: public class Solution { public String longestPalindrome(String s) { int n = s.length(); if (n == 0) return “”; boolean[][] dp = new boolean[n][n]; int start = 0, maxLength = 1; for (int i = 0; i < n; i++) { dp[i][i] = true; } for (int length = 2; length <= n; length++) { for (int i = 0; i < n – length + 1; i++) { int j = i + length – 1; if (s.charAt(i) == s.charAt(j) && (length == 2 || dp[i + 1][j – 1])) { dp[i][j] = true; if (length > maxLength) { start = i; maxLength = length; } } } } return s.substring(start, start + maxLength); } public static void main(String[] args) { Solution sol = new Solution(); String s = “babad”; System.out.println(“Longest Palindromic Substring: ” + sol.longestPalindrome(s)); }} 4. Python: def longestPalindrome(s: str) -> str: n = len(s) if n == 0: return “” dp = [[False] * n for _ in range(n)] start, maxLength = 0, 1 for i in range(n): dp[i][i] = True for length in range(2, n + 1): for i in range(n – length + 1): j = i + length – 1 if s[i] == s[j] and (length == 2 or dp[i + 1][j – 1]): dp[i][j] = True if length > maxLength: start = i maxLength = length return s[start:start + maxLength]# Tests = “babad”print(“Longest Palindromic Substring:”, longestPalindrome(s)) 5. C#: using System;public class Solution { public string LongestPalindrome(string s) { int n = s.Length; if (n == 0) return “”; bool[,] dp = new bool[n, n]; int start = 0, maxLength = 1; for (int i = 0; i < n; i++) { dp[i, i] = true; } for (int length = 2; length <= n; length++) { for (int i = 0; i < n – length + 1; i++) { int j = i + length – 1; if (s[i] == s[j] && (length == 2 || dp[i + 1, j – 1])) { dp[i, j] = true; if (length > maxLength) { start = i; maxLength = length; } } } } return s.Substring(start, maxLength); } public static void Main(string[] args) { Solution sol = new Solution(); string s = “babad”; Console.WriteLine(“Longest Palindromic Substring: ” + sol.LongestPalindrome(s)); }} 6. JavaScript: var longestPalindrome = function(s) { const n = s.length; if (n === 0) return “”; const dp = Array.from({ length: n }, () => Array(n).fill(false)); let start = 0, maxLength = 1; for (let i = 0; i < n; i++) { dp[i][i] = true; } for (let length = 2; length <= n; length++) { for (let i = 0; i < n – length + 1; i++) { const j = i + length – 1; if (s[i] === s[j] && (length === 2 || dp[i + 1][j – 1])) { dp[i][j] = true; if (length > maxLength) { start = i; maxLength = length; } } } } return s.substring(start, start + maxLength);};// Testlet s = “babad”;console.log(“Longest Palindromic Substring:”, longestPalindrome(s)); Summary:

Utilizing Hash Map – O(n) Time and O(n) Space Pre-order TraversalThough instead of linearly looking for every node in the in-order array, we can utilize hashing in line with first technique. Plot the indices of in-order arrays against their values. This will simplify searches from O(n) to O(1). C++ Java Python C# Output 3 4 1 5 2 0

Given pre-order and in-order traversals of a Binary Tree, the challenge is to build the tree and retrieve its root. Table of Content [Naive Approach] Using Pre-order traversal – O(n^2) Time and O(h) Space Pre-order traversal will help one build the tree. Create root node by first element of the pre-order array. In the in-order array, determine this node’s index. Create the left subtree in-order using the components on the left side of the root node. Likewise build the appropriate subtree in-order using the items on the right side of the root node. C++ Java Python C# Output 3 4 1 5 2 0

Making Use of Merge of MergeSortMerge function of Merge sort is supposed to be used here. Consider two sorted arrays, Array 1 and Array 2, together with an empty array, Array 3. Here “i” pointer refers towards 0th index of Array1, similarly “j” and “k” pointer points towards 0th index of Array2 and Array3 for comparisons. C++ C Java Python JavaScript Output 1 2 3 4 5 6 7 8 Time Complexity : O(n1 + n2) Auxiliary Space : O(n1 + n2)

Using Self Balancing BST: C++ C Java Python Output 1 2 3 4 5 6 7 8 Time Complexity: O((n1 + n2)* Log(n1 + n2))Auxiliary Space: O(n1 + n2) for the tree map.

Merging two sorted arrays is the challenge here in a sorted way. Examples:  Input: arr1[] = { 1, 3, 4, 5}, arr2[] = {2, 4, 6, 8} Output: arr3[] = {1, 2, 3, 4, 4, 5, 6, 8} Input: arr1[] = { 5, 8, 9}, arr2[] = {4, 7, 8} Output: arr3[] = {4, 5, 7, 8, 8, 9}  Table of Content The naïve approach to accomplish the same is physical force. Combine all of arr 1’s and arr 2’s components in arr 3. Sort the arr3 then just once more. C++ C Java Python Output 1 2 3 4 5 6 7 8 Time Complexity : O((n1 + n2) log(n1 + n2)) , the whole size of arr3 is m+nAuxiliary Space: O(1)

Storing the width of consecutive 1’s ending at every cell (i, j) in a 2D array is the aim. Beginning from every cell (i, j) with value 1, iterate upwards row by row, determine the minimal width of 1’s in the column to guarantee the rectangle stays valid. The minimal width multiplied by the height yields the size of the rectangle, which updates the maximum area found thus far. Initialize a 2D matrix memo of size nm to hold the width of successive 1s ending at every cell (i, j). Starting at 0 Go iteratively across every cell (i, j) in the input matrix. Should the value at (i, j) be 1, use these guidelines: Should j = 0, set memo[i][j] = 1; otherwise, set memo[i][j] = 1 + memo[i][j – 1]. Define width = memo[i][j]. Update width = min(width, memo[k][j] and get the rectangle area width(i – k + 1) for every row k from i to 0. Add to the maximum area discovered thus far.Get back the computed maximum area. C++ Java Python C# JavaScript Output 8