1813. Sentence Similarity III

Problem

Bài toán yêu cầu kiểm tra xem hai câu có thể được coi là “tương tự” hay không. Hai câu được coi là tương tự nếu có thể biến chúng thành giống hệt nhau bằng cách thêm hoặc xóa một số từ từ đầu hoặc cuối của một trong hai câu

Approach

Phân tách từ

Tách các câu thành danh sách các từ bằng cách sử dụng phương thức .split(” “)

So sánh từ đầu và cuối - Sử dụng two pointer

Một pointer bắt đầu từ đầu danh sách và di chuyển đến khi gặp từ không khớp

Một pointer bắt đầu từ cuối danh sách và di chuyển ngược lại đến khi gặp từ không khớp

Kiểm tra điều kiện

Nếu tổng số từ khớp ở đầu và cuối lớn hơn hoặc bằng độ dài của câu ngắn hơn, thì hai câu được coi là tương tự

Time and space complexity

Độ phức tạp thời gian: O(n)O(n), trong đó nn là độ dài của câu dài hơn. Chỉ cần duyệt qua các từ ở đầu và cuối.

Độ phức tạp không gian: O(n)O(n), do sử dụng mảng để lưu các từ sau khi tách.

Solution

typescripttypescript

1function areSentencesSimilar(sentence1: string, sentence2: string): boolean {
2    let words1 = sentence1.split(" ");
3    let words2 = sentence2.split(" ")
4		 
5		 if(words1.length < words2.length) {
6			 return areSentencesSimilar(sentence2, sentence1)
7		 }
8		 
9		 let left = 0;
10		 let right = 0;
11		 
12		 while (left < words2.length && words1[left] === words2[left]) {
13			 left++;
14		 }
15		 
16		 while(right < words2.length && 
17			 words1[words1.length - 1 - right] === words2[words2.length - 1 - right]) {
18				 right++
19			 }
20		 
21		 
22    return left + right >= words2.length;
23};

Loading content...

1813. Sentence Similarity III

Related Posts

Related Posts

1813. Sentence Similarity III

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists