1813. Sentence Similarity III

Time: O(n)

Space: O(n)

Approach

Split into word arrays; match common prefix and suffix with two pointers; check if shorter is covered.

Key Techniques

The two-pointer technique places pointers at different positions (often the two ends) and moves them toward each other. It turns O(n²) nested loops into O(n) sweeps for problems like pair sums, removing duplicates, and container capacity. Works best on sorted or partitioned arrays.

String

String problems range from simple character counting to complex pattern matching. Common approaches include two pointers, sliding window, prefix hashing, and the KMP algorithm. In C#, strings are immutable — use StringBuilder for efficient concatenation inside loops.

1813.cs

// Approach: Split into word arrays; match common prefix and suffix with two pointers; check if shorter is covered.
// Time: O(n) Space: O(n)

public class Solution
{
    public bool AreSentencesSimilar(string sentence1, string sentence2)
    {
        if (sentence1.Length == sentence2.Length)
            return sentence1.Equals(sentence2);

        string[] words1 = sentence1.Split(' ');
        string[] words2 = sentence2.Split(' ');
        int m = words1.Length;
        int n = words2.Length;
        if (m > n)
            return AreSentencesSimilar(sentence2, sentence1);

        int i = 0; // words1's index
        while (i < m && words1[i].Equals(words2[i]))
            ++i;
        while (i < m && words1[i].Equals(words2[i + n - m]))
            ++i;

        return i == m;
    }
}

Was this solution helpful?