java字符串匹配dp_字符串匹配问题

亦凉 2022-11-06 13:58 136阅读 0赞

递归解法 import java.util.\*;

public class Main \{

//isValid

public static boolean isValid(char\[\] s, char\[\] e) \{

for(int i = 1; i < e.length; i++) \{

if (e\[i\] == '\*' && e\[i - 1\] == '\*')

return false;

return true;

public static boolean judge(char\[\] s, char\[\] e, int si, int ei) \{

if (ei == e.length) \{

return si == s.length;

if (ei + 1 == e.length || e\[ei + 1\] != '\*') \{

return si != s.length && (e\[ei\] == s\[si\] || e\[ei\] == '.')

&& judge(s, e, si + 1, ei + 1);

while (si != s.length && (e\[ei\] == s\[si\] || e\[ei\] == '.')) \{

if (judge(s, e, si, ei + 2)) \{

return true;

si ++;

return judge(s, e, si, ei + 2);

public static void main(String\[\] args) \{

Scanner sc = new Scanner(System.in);

char\[\] s = sc.nextLine().toCharArray();

char\[\] e = sc.nextLine().toCharArray();

sc.close();

if (!isValid(s, e)) \{

System.out.println("NO");

return;

if (!judge(s, e, 0, 0)) \{

System.out.println("NO");

\} else \{

System.out.println("YES");

动态规划解法 import java.util.\*;

public class Main \{

public static boolean isValid(char\[\] s, char\[\] e) \{

for (int i = 0; i < s.length; i++) \{

if (s\[i\] == '\*' || s\[i\] == '.') \{

return false;

for (int i = 0; i < e.length; i++) \{

if (e\[i\] == '\*' && (i == 0 || e\[i - 1\] == '\*')) \{

return false;

return true;

public static boolean isMatchDP(String str, String exp) \{

if (str == null || exp == null) \{

return false;

char\[\] s = str.toCharArray();

char\[\] e = exp.toCharArray();

if (!isValid(s, e)) \{

return false;

boolean\[\]\[\] dp = initDPMap(s, e);

for (int i = s.length - 1; i > -1; i--) \{

for (int j = e.length - 2; j > -1; j--) \{

if(e\[j + 1\] != '\*') \{

dp\[i\]\[j\] = (s\[i\] == e\[j\] || e\[j\] == '.') && dp\[i + 1\]\[j + 1\];

\} else \{

int si = i;

while (si != s.length && (s\[si\] == e\[j\] || e\[j\] == '.')) \{

if (dp\[si\]\[j + 2\]) \{

dp\[i\]\[j\] = true;

break;

si++;

if (dp\[i\]\[j\] != true) \{

dp\[i\]\[j\] = dp\[si\]\[j + 2\];

return dp\[0\]\[0\];

public static boolean\[\]\[\] initDPMap(char\[\] s, char\[\] e) \{

int slen = s.length;

int elen = e.length;

boolean\[\]\[\] dp = new boolean\[slen + 1\]\[elen + 1\];

dp\[slen\]\[elen\] = true;

for (int j = elen - 2; j > -1; j -= 2) \{

if (e\[j\] != '\*' && e\[j + 1\] == '\*') \{

dp\[slen\]\[j\] = true;

\} else \{

break;

if (slen > 0 && elen > 0) \{

if ((e\[elen - 1\] == '.' || s\[slen - 1\] == e\[elen - 1\])) \{

dp\[slen - 1\]\[elen - 1\] = true;

return dp;

public static void main(String\[\] args) \{

Scanner sc = new Scanner(System.in);

String str = sc.nextLine();

String exp = sc.nextLine();

if (isMatchDP(str, exp)) \{

System.out.println("YES");

\} else \{

System.out.println("NO");

java字符串匹配dp_字符串匹配问题

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关增减字符串匹配

相关 java字符串匹配dp_字符串匹配问题

相关 huawei-字符串匹配

相关字符串匹配算法

相关字符串匹配

相关问题 F: 字符串匹配问题

相关字符串匹配

相关 KMP字符串匹配

相关字符串匹配（java）

相关 CCF 字符串匹配