SkylineWebZ

Problem Statement: Regular Expression Matching The task is to implement a function that matches a string with a given regular expression pattern. The pattern can include the following special characters: You need to implement a function that determines whether a given string matches the pattern. Example: Input: Output: Input: Output: Approach: 1. Dynamic Programming Approach: We can use a dynamic programming (DP) approach to solve the problem efficiently. Steps: 2. Time Complexity: Code Implementation C Code: #include <stdio.h>#include <string.h>#include <stdbool.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] || ((p[j-2] == s[i-1] || p[j-2] == ‘.’) && dp[i-1][j]); } else { dp[i][j] = false; } } } return dp[m][n];}int main() { char s[] = “aa”; char p[] = “a*”; if (isMatch(s, p)) { printf(“Match\n”); } else { printf(“No Match\n”); } return 0;} C++ Code: #include <iostream>#include <vector>#include <string>using namespace std;bool isMatch(string s, string p) { int m = s.length(), n = p.length(); 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] || (p[j-2] == s[i-1] || p[j-2] == ‘.’) && dp[i-1][j]; } else { dp[i][j] = false; } } } return dp[m][n];}int main() { string s = “aa”; string p = “a*”; if (isMatch(s, p)) { cout << “Match” << endl; } else { cout << “No Match” << endl; } return 0;} Java Code: 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] || (p.charAt(j – 2) == s.charAt(i – 1) || p.charAt(j – 2) == ‘.’) && dp[i – 1][j]; } else { dp[i][j] = false; } } } return dp[m][n]; } public static void main(String[] args) { Solution solution = new Solution(); String s = “aa”; String p = “a*”; System.out.println(solution.isMatch(s, p)); // Output: true }} Python Code: 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 \ (p[j – 2] == s[i – 1] or p[j – 2] == ‘.’) and dp[i – 1][j] else: dp[i][j] = False return dp[m][n]# Example Usageprint(isMatch(“aa”, “a*”)) # Output: True C# Code: 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] || (p[j – 2] == s[i – 1] || p[j – 2] == ‘.’) && dp[i – 1, j]; } else { dp[i, j] = false; } } } return dp[m, n]; } public static void Main() { Solution solution = new Solution(); Console.WriteLine(solution.IsMatch(“aa”, “a*”)); // Output: True }} JavaScript Code: 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] || (p[j – 2] === s[i – 1] || p[j – 2] === ‘.’) && dp[i – 1][j]; } } } return dp[m][n];};console.log(isMatch(“aa”, “a*”)); // Output: true Summary:

[Space Optimized Approach]: Using Boundary Traversal – O(m*n) Time and O(1) Space Divining the matrix into loops or boundaries allows us to print it in a spiral sequence. First we print the outside boundary elements then we move inward to print the elements of the inner bounds. C++ Java Python c# JavaScript Output 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 Time Complexity: O(m*n), where m and n are the number of rows and columns of the given matrix respectively.Auxiliary Space: O(1).

Print all matrix elements in spiral form given a matrix mat[][] with dimensions m x n. Here are some examples: Table of Content [Naive Approach]: Using Simulation by Visited Matrix – O(m*n) Time and O(m*n) Space Marking the cells that have already been visited helps one to replicate the spiral travel. The movement (right, down, left, up) can be tracked using a direction array; when we come upon a visited cell or the border, we can modify direction. C++ Java Python C# JavaScript Output 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 Time Complexity: O(m*n), where m and n are the number of rows and columns of the given matrix respectively.Auxiliary Space: O(m*n), for the seen matrix and the result vector.

Kadane’s technique works by going from left to right throughout the array and calculating the largest sum of all the subarrays that finish at each element. The highest of these values will be the outcome. The primary problem, however, is how to determine the largest sum of all the subarrays that finish at an element in O(1) time. We can utilize the maximum sum ending at the previous element to get the maximum sum of the subarray ending at the current element, let’s say maxEnding. Therefore, we have two options for any element: C++ C Java Python C# JavaScript Output 11 Time Complexity: O(n), since we are traversing the array only one time.Auxiliary Space: O(1)

Problem Statement: String to Integer (atoi) Implement the function atoi which converts a string to an integer. The function should follow these rules: Example: Example 1: Example 2: Example 3: Example 4: Example 5: Approach: Algorithm: Time Complexity: Code Implementation: C: #include <stdio.h>#include <limits.h>#include <ctype.h>int myAtoi(char* str) { long result = 0; int i = 0, sign = 1; // Skip leading whitespaces while (str[i] == ‘ ‘) i++; // Check for optional sign if (str[i] == ‘+’ || str[i] == ‘-‘) { sign = (str[i] == ‘-‘) ? -1 : 1; i++; } // Convert digits to integer while (isdigit(str[i])) { result = result * 10 + (str[i] – ‘0’); i++; // Check for overflow/underflow if (result * sign > INT_MAX) return INT_MAX; if (result * sign < INT_MIN) return INT_MIN; } return (int)(result * sign);}int main() { char str[] = ” -42″; printf(“%d\n”, myAtoi(str)); return 0;} C++: #include <iostream>#include <climits>#include <cctype>using namespace std;int myAtoi(string str) { long result = 0; int i = 0, sign = 1; // Skip leading whitespaces while (i < str.size() && str[i] == ‘ ‘) i++; // Handle optional sign if (i < str.size() && (str[i] == ‘+’ || str[i] == ‘-‘)) { sign = (str[i] == ‘-‘) ? -1 : 1; i++; } // Convert digits to integer while (i < str.size() && isdigit(str[i])) { result = result * 10 + (str[i] – ‘0’); i++; // Check for overflow/underflow if (result * sign > INT_MAX) return INT_MAX; if (result * sign < INT_MIN) return INT_MIN; } return (int)(result * sign);}int main() { string str = ” -42″; cout << myAtoi(str) << endl; return 0;} Java: public class Solution { public int myAtoi(String str) { long result = 0; int i = 0, sign = 1; // Skip leading whitespaces while (i < str.length() && str.charAt(i) == ‘ ‘) i++; // Handle optional sign if (i < str.length() && (str.charAt(i) == ‘+’ || str.charAt(i) == ‘-‘)) { sign = (str.charAt(i) == ‘-‘) ? -1 : 1; i++; } // Convert digits to integer while (i < str.length() && Character.isDigit(str.charAt(i))) { result = result * 10 + (str.charAt(i) – ‘0’); i++; // Check for overflow/underflow if (result * sign > Integer.MAX_VALUE) return Integer.MAX_VALUE; if (result * sign < Integer.MIN_VALUE) return Integer.MIN_VALUE; } return (int)(result * sign); } public static void main(String[] args) { Solution sol = new Solution(); String str = ” -42″; System.out.println(sol.myAtoi(str)); }} Python: def myAtoi(s: str) -> int: result = 0 sign = 1 i = 0 # Skip leading whitespaces while i < len(s) and s[i] == ‘ ‘: i += 1 # Handle optional sign if i < len(s) and (s[i] == ‘+’ or s[i] == ‘-‘): sign = -1 if s[i] == ‘-‘ else 1 i += 1 # Convert digits to integer while i < len(s) and s[i].isdigit(): result = result * 10 + int(s[i]) i += 1 # Check for overflow/underflow if result * sign > 2**31 – 1: return 2**31 – 1 if result * sign < -2**31: return -2**31 return result * sign# Example usages = ” -42″print(myAtoi(s)) C#: using System;public class Solution { public int MyAtoi(string str) { long result = 0; int i = 0, sign = 1; // Skip leading whitespaces while (i < str.Length && str[i] == ‘ ‘) i++; // Handle optional sign if (i < str.Length && (str[i] == ‘+’ || str[i] == ‘-‘)) { sign = (str[i] == ‘-‘) ? -1 : 1; i++; } // Convert digits to integer while (i < str.Length && Char.IsDigit(str[i])) { result = result * 10 + (str[i] – ‘0’); i++; // Check for overflow/underflow if (result * sign > Int32.MaxValue) return Int32.MaxValue; if (result * sign < Int32.MinValue) return Int32.MinValue; } return (int)(result * sign); } public static void Main() { Solution sol = new Solution(); string str = ” -42″; Console.WriteLine(sol.MyAtoi(str)); }} JavaScript: var myAtoi = function(s) { let result = 0; let sign = 1; let i = 0; // Skip leading whitespaces while (i < s.length && s[i] === ‘ ‘) { i++; } // Handle optional sign if (i < s.length && (s[i] === ‘+’ || s[i] === ‘-‘)) { sign = (s[i] === ‘-‘) ? -1 : 1; i++; } // Convert digits to integer while (i < s.length && /\d/.test(s[i])) { result = result * 10 + (s[i] – ‘0’); i++; // Check for overflow/underflow if (result * sign > 2**31 – 1) return 2**31 – 1; if (result * sign < -(2**31)) return -(2**31); } return result * sign;};// Example usagelet s = ” -42″;console.log(myAtoi(s));

Problem Statement: Given a string s and an integer numRows, arrange the characters of the string in a zigzag pattern on a number of rows and then read the string line by line. The number of rows is given by numRows. You should return the string after the zigzag conversion, which means reading the characters row by row. For example: The zigzag pattern for this example would look like: P A H NA P L S I I GY I R Approach: Algorithm: Time Complexity: Code Implementation: C: #include <stdio.h>#include <string.h>char* convert(char* s, int numRows) { if (numRows == 1 || numRows >= strlen(s)) { return s; } char* result = (char*)malloc(strlen(s) + 1); int index = 0; // Create an array to store rows char rows[numRows][strlen(s)]; for (int i = 0; i < numRows; i++) { memset(rows[i], 0, sizeof(rows[i])); } int row = 0, direction = 1; for (int i = 0; i < strlen(s); i++) { rows[row][i] = s[i]; if (row == 0) direction = 1; if (row == numRows – 1) direction = -1; row += direction; } // Concatenate all rows for (int i = 0; i < numRows; i++) { for (int j = 0; j < strlen(s); j++) { if (rows[i][j] != 0) { result[index++] = rows[i][j]; } } } result[index] = ‘\0’; return result;}int main() { char* s = “PAYPALISHIRING”; int numRows = 3; char* result = convert(s, numRows); printf(“%s\n”, result); free(result); return 0;} C++: #include <iostream>#include <vector>#include <string>using namespace std;string convert(string s, int numRows) { if (numRows == 1 || numRows >= s.size()) return s; vector<string> rows(numRows); int currentRow = 0; bool goingDown = false; for (char c : s) { rows[currentRow] += c; if (currentRow == 0 || currentRow == numRows – 1) goingDown = !goingDown; currentRow += goingDown ? 1 : -1; } string result = “”; for (string row : rows) { result += row; } return result;}int main() { string s = “PAYPALISHIRING”; int numRows = 3; cout << convert(s, numRows) << endl; return 0;} Java: public class ZigzagConversion { public static String convert(String s, int numRows) { if (numRows == 1 || numRows >= s.length()) return s; StringBuilder[] rows = new StringBuilder[numRows]; for (int i = 0; i < numRows; i++) { rows[i] = new StringBuilder(); } int currentRow = 0; boolean goingDown = false; for (char c : s.toCharArray()) { rows[currentRow].append(c); if (currentRow == 0 || currentRow == numRows – 1) goingDown = !goingDown; currentRow += goingDown ? 1 : -1; } StringBuilder result = new StringBuilder(); for (StringBuilder row : rows) { result.append(row); } return result.toString(); } public static void main(String[] args) { String s = “PAYPALISHIRING”; int numRows = 3; System.out.println(convert(s, numRows)); }} Python: def convert(s: str, numRows: int) -> str: if numRows == 1 or numRows >= len(s): return s rows = [”] * numRows currentRow, goingDown = 0, False for c in s: rows[currentRow] += c if currentRow == 0 or currentRow == numRows – 1: goingDown = not goingDown currentRow += 1 if goingDown else -1 return ”.join(rows)# Example usages = “PAYPALISHIRING”numRows = 3print(convert(s, numRows)) C#: using System;using System.Text;public class ZigzagConversion { public static string Convert(string s, int numRows) { if (numRows == 1 || numRows >= s.Length) return s; StringBuilder[] rows = new StringBuilder[numRows]; for (int i = 0; i < numRows; i++) { rows[i] = new StringBuilder(); } int currentRow = 0; bool goingDown = false; foreach (char c in s) { rows[currentRow].Append(c); if (currentRow == 0 || currentRow == numRows – 1) goingDown = !goingDown; currentRow += goingDown ? 1 : -1; } StringBuilder result = new StringBuilder(); foreach (var row in rows) { result.Append(row.ToString()); } return result.ToString(); } public static void Main() { string s = “PAYPALISHIRING”; int numRows = 3; Console.WriteLine(Convert(s, numRows)); }} JavaScript: var convert = function(s, numRows) { if (numRows === 1 || numRows >= s.length) return s; let rows = Array(numRows).fill(”); let currentRow = 0; let goingDown = false; for (let i = 0; i < s.length; i++) { rows[currentRow] += s[i]; if (currentRow === 0 || currentRow === numRows – 1) goingDown = !goingDown; currentRow += goingDown ? 1 : -1; } return rows.join(”);};// Example usagelet s = “PAYPALISHIRING”;let numRows = 3;console.log(convert(s, numRows));

What is this problem with N-Queen? Placing N chess queens on a N×N chessboard without any queens attacking one another is known as the N Queen problem. For example, the following is a solution for the 4 Queen problem. The anticipated result takes the shape of a matrix with “Qs” for the blocks containing queens and “.” for the empty spaces. For instance, the output matrix for the 4-Queen solution mentioned above looks like this. N Queen Problem using Backtracking: Starting with the leftmost column, the queens are supposed to be arranged one after the other in various columns. We look for conflicts with other queens before positioning a queen in a column. We mark a row and column in the current column as part of the solution if we locate a row for which there is no collision. We go back and return false if we are unable to locate such a row because of clashes. To put the concept into practice, take the actions listed below: C++ C Java Python C# Time Complexity: O(N!)Auxiliary Space: O(N2)

Given an array of words, print all anagrams together. Making a hash table is an easy way. Determine the hash value of every word so that the hash value of every anagram is the same. Add these hash values to the Hash Table. Lastly, use the same hash values to print those words together. The modulo sum of all characters’ ASCII values can serve as a basic hashing technique. Two non-anagram words may have the same hash value when modulo sum is used. Individual characters must be matched in order to manage this. Here’s another way to print all the anagrams at once. Consider the word array, index array, and two auxiliary arrays. Add the specified word sequence to the word array. The word array’s individual words are sorted. Lastly, sort the word array while monitoring the associated indices. All of the anagrams group together after sorting. To print the strings from the initial array of strings, use the index array. Let’s use the following word sequence as input to better understand the steps: “cat”, “dog”, “tac”, “god”, “act” 1) Create two auxiliary arrays index[] and words[]. Copy all given words to words[] and store the original indexes in index[]  index[]: 0 1 2 3 4 words[]: cat dog tac god act 2) Sort individual words in words[]. Index array doesn’t change. index[]: 0 1 2 3 4 words[]: act dgo act dgo act 3) Sort the words array. Compare individual words using strcmp() to sort index: 0 2 4 1 3 words[]: act act act dgo dgo 4) All anagrams come together. But words are changed in the words array. To print the original words, take the index from the index array and use it in the original array. We get  “cat tac act dog god” The aforesaid algorithm’s implementations are shown below. Both index and word arrays are stored in an array of structure “Word” in the program that follows. Another structure that holds an array of “Word” structures is called Dupray. C C++ Java Python C# JavaScript Results: Cat tac act dog god Time Complexity: Assume that there are N words with a maximum of M characters per word. O(NMLogM + MNLogN) is the upper bound.O(NMLogM) time is required for step 2. Word sorting requires a maximum of O(MLogM) time. Thus, it takes O(NMLogM) time to sort N-words. O(MNLogN) is taken in step 3. Sorting a word array requires NLogN comparisons. Maximum O(M) time may be required for a comparison. Thus, O(MNLogN) will be the time required to sort a word array. Complexity of space: O(N*M)