Sponsored
Sponsored
The Two Pointers technique involves using two indices that move towards each other from the start and end of the lists. This approach effectively captures the prefixes and suffixes.
By using two pointers, we move from the start to the first words that don't match and from the end to the first words that also don't match. If the pointers end up crossing or are equal, the sentences are considered similar. We exploit the fact that any dissimilar portion in the middle, if any, can be 'inserted'.
Time Complexity: O(n + m), where n and m are the lengths of sentence1 and sentence2 respectively.
Space Complexity: O(n + m) for storing words.
1#include <string>
2#include <vector>
3
4using namespace std;
5
6bool areSentencesSimilar(string sentence1, string sentence2) {
7 vector<string> s1_words, s2_words;
8 stringstream ss1(sentence1), ss2(sentence2);
9 string word;
10
11 while(ss1 >> word) {
12 s1_words.push_back(word);
13 }
14
15 while(ss2 >> word) {
16 s2_words.push_back(word);
17 }
18
19 int i = 0, j = 0;
20
21 while (i < s1_words.size() && i < s2_words.size() && s1_words[i] == s2_words[i]) {
22 i++;
23 }
24
25 while (j < s1_words.size() - i && j < s2_words.size() - i &&
26 s1_words[s1_words.size() - j - 1] == s2_words[s2_words.size() - j - 1]) {
27 j++;
28 }
29
30 return (i + j >= s1_words.size() || i + j >= s2_words.size());
31}
32This solution uses stringstream to split words and vector data structures to store them. Two pointers traverse the words from the start and end to check for alignment conditions.
Another approach is to utilize a dynamic programming table to store sub-problems results. You can construct a DP table where dp[i][j] indicates whether the first i words from sentence1 can match the first j words from sentence2. This could be expanded using insertion strategies for any non-matching sub-sequences.
This approach relies more on systematic computation than geometric traversal, but can be more memory intensive.
Time Complexity: O(n*m)
Space Complexity: O(n*m)
public class Solution {
public bool AreSentencesSimilar(string sentence1, string sentence2) {
string[] s1_words = sentence1.Split(' ');
string[] s2_words = sentence2.Split(' ');
bool[,] dp = new bool[s1_words.Length + 1, s2_words.Length + 1];
dp[0, 0] = true;
for (int i = 0; i <= s1_words.Length; i++) {
for (int j = 0; j <= s2_words.Length; j++) {
if (i > 0 && j > 0 && s1_words[i-1] == s2_words[j-1]) {
dp[i, j] = dp[i-1, j-1];
}
else if (i > 0) {
dp[i, j] = dp[i-1, j] || dp[i, j];
}
else if (j > 0) {
dp[i, j] = dp[i, j-1] || dp[i, j];
}
}
}
return dp[s1_words.Length, s2_words.Length];
}
}
In C#, the DP matrix is handled using a two-dimensional boolean array, with loops used to determine matching possibilities or strategic insertions.