Welcome to Day 35 of my 100 Days of DSA challenge! Today, I tackled some advanced dynamic programming problems that involve string manipulation and pattern matching. From solving the "word break" and "interleaving strings" problems to addressing challenging problems like "longest palindromic substring" and "regular expression matching," today's tasks pushed the boundaries of DP and string algorithms.
Check out my GitHub repository for all the solutions and progress updates at: 100 Days of DSA
Let’s dive into how I approached these complex problems and the solutions I developed. 🚀
1. Word Break Problem
This program solves the "word break" problem using dynamic programming. It checks whether a string can be broken down into valid words from a given dictionary. The dynamic programming array dp[i] is used, where each dp[i] indicates whether the substring str[0...i-1] can be segmented into dictionary words. Initially, dp[0] is set to true, indicating that an empty string is considered valid. The program then checks each substring of the string str and updates the dp array accordingly. The final answer is stored in dp[n], where n is the length of the string.
Code:
#include <iostream>
#include <cstring>
#include <unordered_set>
using namespace std;
#define MAX 1000
// Function to check if a word can be broken down into valid words from the dictionary
bool word_break(char str[], unordered_set<string>& dict, int n) {
bool dp[MAX] = {false}; // dp[i] will be true if str[0...i-1] can be segmented
dp[0] = true; // Empty string is always considered as segmented
// Traverse the string and check each substring
for (int i = 1; i <= n; i++) {
// Check all substrings ending at i
for (int j = 0; j < i; j++) {
if (dp[j] && dict.find(string(str + j, str + i)) != dict.end()) {
dp[i] = true;
break;
}
}
}
return dp[n]; // The result for the entire string
}
int main() {
char str[MAX];
int n;
cout << "Enter the string: ";
cin >> str;
unordered_set<string> dict = {"apple", "pie", "applepie"};
n = strlen(str);
if (word_break(str, dict, n)) {
cout << "The string can be segmented into words from the dictionary." << endl;
} else {
cout << "The string cannot be segmented into words from the dictionary." << endl;
}
return 0;
}
Output:
2. Interleaving Strings Problem
This program checks whether a third string (str3) can be formed by interleaving two other strings (str1 and str2). A dynamic programming table (dp) is used to store the results of subproblems, where dp[i][j] indicates if the first i characters of str1 and the first j characters of str2 can form the first i + j characters of str3. The solution builds up the table by checking each character of str1 and str2 to see if it matches the corresponding character in str3.
Code:
#include <iostream>
#include <cstring>
using namespace std;
#define MAX 1000
// Function to check if two strings can be interleaved to form a third string
bool is_interleave(char str1[], char str2[], char str3[], int len1, int len2, int len3) {
if (len1 + len2 != len3) {
return false; // If lengths don't match, return false
}
bool dp[MAX][MAX]; // 2D DP array
// Initialize the DP table
for (int i = 0; i <= len1; i++) {
for (int j = 0; j <= len2; j++) {
dp[i][j] = false;
}
}
// Base case: both strings are empty
dp[0][0] = true;
// Fill the dp table
for (int i = 0; i <= len1; i++) {
for (int j = 0; j <= len2; j++) {
if (i > 0 && str1[i - 1] == str3[i + j - 1]) {
dp[i][j] = dp[i][j] || dp[i - 1][j]; // If char from str1 matches
}
if (j > 0 && str2[j - 1] == str3[i + j - 1]) {
dp[i][j] = dp[i][j] || dp[i][j - 1]; // If char from str2 matches
}
}
}
// The answer is in the bottom-right corner of the table
return dp[len1][len2];
}
int main() {
char str1[MAX], str2[MAX], str3[MAX];
cout << "Enter the first string: ";
cin >> str1;
cout << "Enter the second string: ";
cin >> str2;
cout << "Enter the third string: ";
cin >> str3;
int len1 = strlen(str1);
int len2 = strlen(str2);
int len3 = strlen(str3);
if (is_interleave(str1, str2, str3, len1, len2, len3)) {
cout << "The third string is an interleaving of the first and second strings." << endl;
} else {
cout << "The third string is NOT an interleaving of the first and second strings." << endl;
}
return 0;
}
Output:
3. Longest Palindromic Substring
This program finds the longest palindromic substring in a given string using dynamic programming. It utilizes a 2D array dp to track whether a substring from index i to j is a palindrome. It starts by considering all substrings of length 1 (which are always palindromes), then it checks substrings of length 2, and continues expanding to longer substrings. For each substring, it checks if the first and last characters are the same and if the inner substring is also a palindrome.
Code:
#include <iostream>
#include <cstring>
using namespace std;
#define MAX 1000
// Function to find the longest palindromic substring
int longest_palindromic_substring(char str[], int n) {
bool dp[MAX][MAX]; // 2D array to store the palindrome status for substrings
int max_length = 1, start = 0; // To store the length and start index of the longest palindrome found
// All substrings of length 1 are palindromes
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
// Check for substrings of length 2
for (int i = 0; i < n - 1; i++) {
if (str[i] == str[i + 1]) {
dp[i][i + 1] = true;
max_length = 2;
start = i;
}
}
// Check for substrings of length 3 and greater
for (int length = 3; length <= n; length++) {
for (int i = 0; i < n - length + 1; i++) {
int j = i + length - 1; // Ending index of the current substring
// If the first and last characters match, check if the middle substring is a palindrome
if (str[i] == str[j] && dp[i + 1][j - 1]) {
dp[i][j] = true;
// Update max length and start index if a longer palindrome is found
if (length > max_length) {
max_length = length;
start = i;
}
}
}
}
// Return the length of the longest palindromic substring
return max_length;
}
int main() {
char str[MAX];
cout << "Enter the string: ";
cin >> str;
int n = strlen(str);
int max_length = longest_palindromic_substring(str, n);
cout << "Length of the Longest Palindromic Substring: " << max_length << endl;
return 0;
}
Output:
4. Wildcard Matching Problem
This program uses dynamic programming to solve the wildcard matching problem, where the pattern may contain ? (matches any single character) and * (matches any sequence of characters). A 2D dp table is used, where dp[i][j] is true if the substring s[0..i-1] matches the pattern p[0..j-1]. The base cases handle matching empty strings with patterns, and for each character in the string and pattern, we update the table based on whether the current character matches or is a wildcard. Finally, dp[m][n] gives the result for the full string and pattern.
Code:
#include <iostream>
#include <cstring>
using namespace std;
#define MAX 1000
// Function to perform wildcard matching using dynamic programming
bool wildcard_matching(char s[], char p[], int m, int n) {
bool dp[MAX][MAX]; // 2D array to store whether substrings match
// Initialize dp array
dp[0][0] = true; // Empty pattern and empty string match
// Fill first row (pattern with only '*' characters can match empty string)
for (int j = 1; j <= n; j++) {
dp[0][j] = (p[j - 1] == '*') && dp[0][j - 1];
}
// Fill the dp array for the rest of the strings and pattern
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]; // Characters match or '?' matches any character
}
else if (p[j - 1] == '*') {
dp[i][j] = dp[i - 1][j] || dp[i][j - 1]; // '*' matches zero or more characters
}
else {
dp[i][j] = false; // If characters don't match and no wildcard
}
}
}
return dp[m][n]; // Final result for matching full strings
}
int main() {
char s[MAX], p[MAX];
cout << "Enter the string: ";
cin >> s;
cout << "Enter the pattern: ";
cin >> p;
int m = strlen(s);
int n = strlen(p);
if (wildcard_matching(s, p, m, n)) {
cout << "The pattern matches the string." << endl;
} else {
cout << "The pattern does not match the string." << endl;
}
return 0;
}
Output:
5. Solve the "regular expression matching" problem using dynamic programming.
This program uses dynamic programming (DP) to solve the regular expression matching problem. It uses a 2D DP table dp[i][j] where i represents the length of the string considered and j represents the length of the pattern considered. The table is filled according to the following rules:
If the current character of the string matches the current character of the pattern, or if the pattern character is a dot (
.), then the DP value depends on the previous substring matches.If the pattern character is an asterisk (
*), it either matches zero or more characters based on the preceding character in the pattern.The base case
dp[0][0]istrue, indicating an empty string matches an empty pattern.
The final result of whether the string matches the full pattern is stored in dp[str_len][pat_len].
Code:
#include <iostream>
#include <cstring>
using namespace std;
#define MAX 1000
// Function to check if the string matches the given regular expression
bool isMatch(const char str[], const char pattern[], int str_len, int pat_len) {
bool dp[MAX][MAX]; // DP table to store results of subproblems
// Initialize DP table
dp[0][0] = true;
// Fill the first row (matching empty string with pattern)
for (int j = 1; j <= pat_len; j++) {
if (pattern[j - 1] == '*') {
dp[0][j] = dp[0][j - 2]; // '*' can match zero characters
}
}
// Fill the DP table
for (int i = 1; i <= str_len; i++) {
for (int j = 1; j <= pat_len; j++) {
if (pattern[j - 1] == str[i - 1] || pattern[j - 1] == '.') {
dp[i][j] = dp[i - 1][j - 1]; // Characters match or '.' matches any character
} else if (pattern[j - 1] == '*') {
dp[i][j] = dp[i][j - 2]; // '*' can match zero characters
if (pattern[j - 2] == str[i - 1] || pattern[j - 2] == '.') {
dp[i][j] = dp[i][j] || dp[i - 1][j]; // '*' can match more than one character
}
} else {
dp[i][j] = false; // No match if current characters do not match
}
}
}
return dp[str_len][pat_len]; // Return the result of matching full string with full pattern
}
int main() {
char str[MAX], pattern[MAX];
cout << "Enter the string: ";
cin >> str;
cout << "Enter the pattern: ";
cin >> pattern;
int str_len = strlen(str);
int pat_len = strlen(pattern);
if (isMatch(str, pattern, str_len, pat_len)) {
cout << "The string matches the pattern." << endl;
} else {
cout << "The string does not match the pattern." << endl;
}
return 0;
}
Output:
Day 35 delved into advanced dynamic programming concepts, tackling complex string matching and palindromic problems. By applying DP to challenges like word break, interleaving strings, and wildcard matching, I gained deeper insights into optimizing solutions for intricate problems. This reinforced the power of dynamic programming in handling sophisticated real-world scenarios efficiently. 🚀