请选择 进入手机版 | 继续访问电脑版
搜索
房产
装修
汽车
婚嫁
健康
理财
旅游
美食
跳蚤
二手房
租房
招聘
二手车
教育
茶座
我要买房
买东西
装修家居
交友
职场
生活
网购
亲子
情感
龙城车友
找美食
谈婚论嫁
美女
兴趣
八卦
宠物
手机

LeetCode10. Regular Expression Matching

[复制链接]
查看: 88|回复: 0

9747

主题

1万

帖子

3万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
37523
发表于 2019-11-9 10:28 | 显示全部楼层 |阅读模式
  题目:题目链接
  题意:给出两个字符串s和p,问能否可以大要完全婚配,其中s只包含小写字母,p除了大要包含小写字母外还含有字符'.'和'*','.'可以婚配尽情字母,'*'表示其前面的那个字符可以有尽情个(可以为0个)
  思绪:类比LCS(最长公共子序列)题目,我们很轻易想到该题的静态计划解题思绪。对于该题我们采取二维dp,dp[j]表示s前i个字符能否可以与p前j个字符完全婚配,递推关系以下:
    1)  dp[0][0]=true;    
    2)  假如j > 1 && p[j - 1] == '*':dp[j] = dp[j - 2] || (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j]);
    3)  else :dp[j] = i > 0 && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
  PS:重新刷题立马又感遭到了英语对我深深的恶意,一路头又把题目读错了,以为只要s是p扩容后的子序列就行,间接致使第一次在leetcode上功劳熟悉的wrong answer一枚,看了题解才发现读错了题,我真是太沙雕了
  ac代码以下:
  1. 1 class Solution { 2 public: 3     bool isMatch(string s, string p) { 4         int n = s.size(), m = p.size(); 5         vector< vector > ans(n + 1, vector(m + 1, false) ); 6         ans[0][0] = true; 7         for(int i = 0; i  0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.') && ans[i - 1][j]);11                 else12                     ans[i][j] = i > 0 && ans[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');13             }14         }15         return ans[n][m];16     }17 };
复制代码


免责声明:假如加害了您的权益,请联系站长,我们会实时删除侵权内容,感谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Copyright © 2006-2014 妈妈网-中国妈妈第一,是怀孕、育儿、健康等知识交流传播首选平台 版权所有 法律顾问:高律师 客服电话:0791-88289918
技术支持:迪恩网络科技公司  Powered by Discuz! X3.2
快速回复 返回顶部 返回列表