面试官给我个字符串问里面有多少个"bigsai"子序列给我难住了

 本文转载自微信公众号「bigsai」，作者bigsai。转载本文请联系bigsai公众号。

林芝网站制作公司哪家好，找创新互联！从网页设计、网站建设、微信开发、APP开发、成都响应式网站建设等网站项目制作，到程序开发，运营维护。创新互联自2013年创立以来到现在10年的时间，我们拥有了丰富的建站经验和运维经验，来保证我们的工作的顺利进行。专注于网站建设就选创新互联。

前言

一次面试官笑嘻嘻的问我一个问题，场景还原一下：

然后我把这个问题透彻的研究了一下，并由浅入深的分析了一下这种问题的思路，分别是有几个pat和不同子序列问题。

有几个pat

这是pat的一道题。

分析

如何求一个字符串中有多少个pat。不要想着三重for循环去枚举所有情况了，那不是好的方法。这这种题如果有灵感的话应该能猜出来这应该是一种动态规划的问题。

首先将问题简单分解一下，如果问原串中有多少个p。那么很容易枚举一遍即可。例如序列ppp就是三个p。

如果带上a，求串pa的个数呢?pa是由p和a组成。求pa的个数肯定和a有很大的关系，每个a可能会组成若干个pa取决于这个a前面p的数量。将所有a位置组成的pa相加即可。例如pppapa 总共可以组合3+4=7个pa.

同理想知道有几个pat那也很容易啊，pat的求解需要找到每个t，然后知道当前位置前面有多少个pa，叠加求解获得结果即可。结合下图流程看更好。

不同的子序列

题目描述：

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些(也可以不删除)字符且不干扰剩余字符相对位置所组成的新字符串。(例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是)

题目数据保证答案符合 32 位带符号整数范围。

示例 1：

 
 
 
 
    
  
  
  
  
  1. 输入：s = "rabbbit", t = "rabbit" 
    2. 
  
  
  
  
  2. 输出：3 
    3. 
  
  
  
  
  3. 解释： 
    4. 
  
  
  
  
  4. 如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。 
    5. 
  
  
  
  
  5. (上箭头符号 ^ 表示选取的字母) 
    6. 
  
  
  
  
  6. rabbbit 
    7. 
  
  
  
  
  7. ^^^^ ^^ 
    8. 
  
  
  
  
  8. rabbbit 
    9. 
  
  
  
  
  9. ^^ ^^^^ 
    10. 
  
  
  
  
  10. rabbbit 
    11. 
  
  
  
  
  11. ^^^ ^^^ 
    12.

示例 2：

 
 
 
 
    
  
  
  
  
  1. 输入：s = "babgbag", t = "bag" 
    2. 
  
  
  
  
  2. 输出：5 
    3. 
  
  
  
  
  3. 解释： 
    4. 
  
  
  
  
  4. 如下图所示, 有 5 种可以从 s 中得到 "bag" 的方案。  
    5. 
  
  
  
  
  5. (上箭头符号 ^ 表示选取的字母) 
    6. 
  
  
  
  
  6. babgbag 
    7. 
  
  
  
  
  7. ^^ ^ 
    8. 
  
  
  
  
  8. babgbag 
    9. 
  
  
  
  
  9. ^^    ^ 
    10. 
  
  
  
  
  10. babgbag 
    11. 
  
  
  
  
  11. ^    ^^ 
    12. 
  
  
  
  
  12. babgbag 
    13. 
  
  
  
  
  13.   ^  ^^ 
    14. 
  
  
  
  
  14. babgbag 
    15. 
  
  
  
  
  15.     ^^^ 
    16.

提示：

 
 
 
 
    
  
  
  
  
  1. 0 <= s.length, t.length <= 1000 
    2. 
  
  
  
  
  2.  
    3. 
  
  
  
  
  3. s 和 t 由英文字母组成 
    4.

分析：

这个问题其实就是上面有几个pat的变形拓展，其基本思想其实是一致的，上面那题问的是有几个pat，固定、且很短。但这里面t串的长度不固定，所以处理上就要使用数组来处理而不能直接if else。

这题的思路肯定也是动态规划dp了，dp[j]的意思就是t串中[0,j-1]长字符在s中能够匹配的数量(当然这个值从前往后是动态变化的)，数组大小为dp[t.length+1]。在遍历s串的每一个元素都要和t串中所有元素进行对比看看是否相等，如果s串枚举到的这个串和t串中的第j个相等。那么dp[j+1]+=dp[j]。你可能会问为啥是dp[j+1],因为第一个元素匹配到需要将数量+1，而这里为了避免(判断是否为首字符)这样的判断我们将dp[0]=1,这样t串的每个元素都能正常的操作。

但是有一点需要注意的就是在遍历s串中第i个字母的时候，遍历t串比较不能从左向右而必须从右向左。因为在遍历s串的第i个字符在枚举dp数组时候要求此刻数据是相对静止的叠加(即同一层次不能产生影响)，而从左往右进行遇到相同字符会对后面的值产生影响。区别的话可以参考下图这个例子：

实现的代码为：

 
 
 
 
    
  
  
  
  
  1. class Solution { 
    2. 
  
  
  
  
  2.     public int numDistinct(String s, String t) { 
    3. 
  
  
  
  
  3.        char s1[]=s.toCharArray(); 
    4. 
  
  
  
  
  4.         char t1[]=t.toCharArray(); 
    5. 
  
  
  
  
  5.  
    6. 
  
  
  
  
  6.         int dp[]=new int[t1.length+1]; 
    7. 
  
  
  
  
  7.         dp[0]=1;//用来叠加 
    8. 
  
  
  
  
  8.  
    9. 
  
  
  
  
  9.         for(int i=0;i
  
  
  
  
  10.         { 
    11. 
  
  
  
  
  11.             for(int j=t1.length-1;j>=0;j--) 
    12. 
  
  
  
  
  12.             { 
    13. 
  
  
  
  
  13.                 if(t1[j]==s1[i]) 
    14. 
  
  
  
  
  14.                 { 
    15. 
  
  
  
  
  15.                     dp[j+1]+=dp[j]; 
    16. 
  
  
  
  
  16.                 } 
    17. 
  
  
  
  
  17.             } 
    18. 
  
  
  
  
  18.         } 
    19. 
  
  
  
  
  19.         return dp[t1.length]; 
    20. 
  
  
  
  
  20.     } 
    21. 
  
  
  
  
  21. } 
    22.

网站名称：面试官给我个字符串问里面有多少个"bigsai"子序列给我难住了
文章路径：http://www.gawzjz.com/qtweb/news13/183063.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

搜索引擎优化知识

分类信息网

成都app开发　　 　香港云虚拟主机　　 　成都营销网站制作　　 　企业网站建设公司　　 　APP定制开发　　 　成都400电话办理　　 　四川成都做网站　　 　乐山石膏隔墙　　 　网站seo优化　　 　重庆外贸网站建设　　 　成都app软件开发　　 　绵阳网站建设公司　　 　微信小程序　　 　成都网站设计　　 　成都发电机维修　　 　红锐电子　　 　网站建设开发　　 　网站维护　　 　成都网络营销　　 　成都商城app开发