LeetCode 1813 句子相似性【双指针】 HERODING的LeetCode之路

2024-07-16 13:47| 来源: 网络整理| 查看: 265

在这里插入图片描述

解题思路：非常经典的一道双指针问题，根据题意，相似句子即表示，短的句子可以拆分构成长的句子的头尾，但是要注意，是单词拆分，而不是字符。由于C++中没有直接拆分单词的函数，所以我先想到的是通过字符匹配，方法自然是双指针，分别指向短的句子的头尾，判断是否能够和长的句子的头尾进行匹配，结果是越写越复杂，因为字符匹配的话会有很多的特殊情况，比如匹配的单词不完整，短的句子只有一个单词等等，还不如编写一个单词拆分函数，然后单词匹配呢。所以最终解法如下：

编写单词拆分函数，利用stringstream把单词一个个放入vector中；定义双指针指向短句子的头尾单词；两个while循环分别从左往右和从右往左匹配单词；最后判断是否覆盖整个短句子。

代码如下：

class Solution { public: bool areSentencesSimilar(string sentence1, string sentence2) { int n1 = sentence1.size(), n2 = sentence2.size(); if(n1 > n2) { return areSentencesSimilar(sentence2, sentence1); } vector s1 = split(sentence1); vector s2 = split(sentence2); n1 = s1.size(), n2 = s2.size(); int left = 0, right = n1 - 1; while(left right --; } return left + n1 - right - 1 == n1; } vector split(string s) { vector ans; stringstream ss; ss s) ans.push_back(s); return ans; } };

【本文地址】

公司简介

联系我们