Skip to content

Latest commit

 

History

History
 
 

392.Is-Subsequence

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 

392.Is-Subsequence

普通的双指针解法就不再赘述。考虑follow up的问题。显然,需要提前建立关于t的一些信息的存储,方便s来查阅,用空间换时间嘛。

结合双指针解法的思路,如果在t[pos]找到了s[i],则只需要在pos之后去寻找s[i+1]。所以提前构建映射:t的每个字符和该字符出现位置:

Map[s[i]].push_back(i);

建立pos的初始位置-1. 然后遍历s[i]:在Map[s[i]]里找第一个大于pos的位置并更新pos,则之后对于s[i+1]的查找必须从t的新pos位置开始。

int pos=-1;
for (int i=0; i<s.size()-1; i++)
{
   int flag=0;
   for (int j: Map[s[i]])
   {
      if (j>pos)
      {
         pos = j;
         flag = 1;
      }
   }
   if (flag==0) retrun false; // 对于s[i],在t中没有找到合适的位置
}
return true;

Leetcode Link