Sentence Similarity III

MediumArrayTwo PointersString

Solution

Solution1: Deque

export function areSentencesSimilar(sentence1: string, sentence2: string): boolean {
  const words1 = sentence1.split(' ');
  const words2 = sentence2.split(' ');
  while (0 < words1.length && 0 < words2.length && words1[0] === words2[0]) {
    words1.shift();
    words2.shift();
  }
  while (
    0 < words1.length &&
    0 < words2.length &&
    words1[words1.length - 1] === words2[words2.length - 1]
  ) {
    words1.pop();
    words2.pop();
  }
  return words1.length === 0 || words2.length === 0;
}

Complexity

  • Time: O(M + N)
  • Space: O(M + N)

Solution2: Two Pointer

export function areSentencesSimilar(sentence1: string, sentence2: string): boolean {
  let words1 = sentence1.split(' ');
  let words2 = sentence2.split(' ');
  if (words1.length > words2.length) {
    [words1, words2] = [words2, words1];
  }
 
  let [start, end1, end2] = [0, words1.length - 1, words2.length - 1];
  while (start < words1.length && words1[start] === words2[start]) {
    start += 1;
  }
  while (0 <= end1 && words1[end1] === words2[end2]) {
    end1 -= 1;
    end2 -= 1;
  }
  return end1 < start;
}

Complexity

  • Time: O(M + N)
  • Space: O(M + N)