LeetCode 1813: Sentence Similarity III
Problem Description
Explanation:
To solve this problem, we can follow these steps:
- Split both sentences into individual words.
- Check if either sentence1 is a substring of sentence2 or vice versa. If so, return true.
- Iterate through the words of sentence1 and sentence2 simultaneously. If at any point the words differ, we try to find a common prefix and suffix that can be inserted to make the sentences similar.
- If no common prefix or suffix is found, return false.
Time complexity: O(n) where n is the maximum length of the two input sentences. Space complexity: O(n) where n is the maximum length of the two input sentences.
:
Solutions
class Solution {
public boolean areSentencesSimilar(String sentence1, String sentence2) {
String[] words1 = sentence1.split(" ");
String[] words2 = sentence2.split(" ");
if (sentence1.contains(sentence2) || sentence2.contains(sentence1)) {
return true;
}
int i = 0, j = 0;
int m = words1.length, n = words2.length;
while (i < m && j < n && words1[i].equals(words2[j])) {
i++;
j++;
}
while (i < m && j < n && words1[m - 1].equals(words2[n - 1])) {
m--;
n--;
}
return i == m && j == n;
}
}Loading editor...