题目

1813. 句子相似性 III【中等】

题解

字符串按空格分割+双指针

1. 按空格分割两个句子，得到字符串数组word1和word2
   （一定能通过往其中一个字符串数组中插入某个字符串数组，得到另一个字符串数组）
2. 双指针：
   i 表示两个字符串数组从左开始，最多有 i 个字符串相同。
   j 表示剩下的字符串数组从右开始，最多有 j 个字符串相同。
3. 如果 i+j 正好是某个字符串数组的长度，那么原字符串就是相似的。

class Solution {
    public boolean areSentencesSimilar(String sentence1, String sentence2) {
        //空格分割
        String[] word1=sentence1.split(" ");
        String[] word2=sentence2.split(" ");
        int i=0,j=0,n1=word1.length,n2=word2.length;
        //双指针
        while(i<n1&&i<n2&&word1[i].equals(word2[i]))
            i++;
        //为了让两字符串数组末端对齐，j从0开始，比较下标为n-1-j
        //下标要>=i，因此n-1-j>=i，得到j的范围
        while(j<=n1-i-1&&j<=n2-i-1&&word1[n1-j-1].equals(word2[n2-j-1]))
            j++;
        System.out.println(i+" "+j);
        return i+j==Math.min(n1,n2);
    }
}

时间复杂度：$O(n1+n2)$

空间复杂度：$O(n1+n2)$