个人网站设计论文参考文献,wordpress点餐,论坛网站模块,网站更新seo题目 给你一个字符串数组(每个字符串均由小写字母组成)和一个字符规律#xff08;由小写字母和.和组成)#xff0c;识别数组中哪些字符串可以匹配到字符规律上。.“匹配任意单个字符#xff0c;”*匹配零个或多个前面的那一个元素#xff0c;所谓匹配#xff…题目 给你一个字符串数组(每个字符串均由小写字母组成)和一个字符规律由小写字母和.和组成)识别数组中哪些字符串可以匹配到字符规律上。.“匹配任意单个字符”*匹配零个或多个前面的那一个元素所谓匹配是要涵盖整个字符串的而不是部分字符串。 输入描述: 第一行为空格分割的多个字符串1单个字符串长度1001字符串个数100 第二行为字符规律1字符规律长度50 不需要考虑异常场景 输出描述: 匹配的字符串在数组中的下标从0开始)多个匹配时下标升序并用,分割若均不匹配输出-1 示例1: 输入 ab aab .* 输出 0,1 思路
正则匹配 匹配模式加上首尾限定^$可判断是否完全匹配 动态规划
同leetcode10. 正则表达式匹配 不利用正则匹配使用动态规划可判断当前字符s是否和给定匹配模式p完全匹配。 dp[i][j]定义s[:i]和p[:j]匹配是否匹配其中s[:i]代表s的前i个字符s[:0]代表取0个s的字符 初始化dp[0][0]1空字符串和空模式是匹配的所以为1。考虑s为空pa*b*c*的模式当p的偶数位为*时dp[0][j]dp[0][j-2] 递推关系根据当前p的字符是否为*判断只有以下情况dp[i][j]才可能为1标黄色部分匹配即可 如果p[j-1] * dp[i][j - 2] 1如s a p a b* dp[i-1][j] 1s[i-1]p[j-2]如s abb p ab* dp[i-1][j] 1‘.’p[j-2]如s abb p a.* 如果p[j-1] * dp[i-1][j-1] 1‘.’p[j-1]如s ab p a. dp[i-1][j-1] 1s[i-1]p[j-1]如s ab p ab 题解
package hwod;import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class StrMatch {public static void main(String[] args) {Scanner sc new Scanner(System.in);String[] strArr sc.nextLine().split( );String p sc.nextLine();ListInteger res strMatch2(strArr, p);if (res.size() 0) {System.out.println(-1);return;}for (int i 0; i res.size(); i) {if (i ! 0) System.out.print(,);System.out.print(res.get(i));}}//方案一正则匹配private static ListInteger strMatch(String[] strArr, String p) {ListInteger res new ArrayList();p ^ p $;for (int i 0; i strArr.length; i) {if (strArr[i].matches(p)) {res.add(i);}}return res;}//方案二动态规划private static ListInteger strMatch2(String[] strArr, String p) {ListInteger res new ArrayList();for (int i 0; i strArr.length; i) {if (checked(strArr[i], p)) {res.add(i);}}return res;}private static boolean checked(String s, String p) {int m s.length() 1, n p.length() 1;int[][] dp new int[m][n]; //s[:i]和p[:j]匹配dp[0][0] 1;for (int i 2; i n; i 2) {if (p.charAt(i - 1) *) dp[0][i] dp[0][i - 2];}for (int i 1; i m; i) {for (int j 1; j n; j) {if (p.charAt(j - 1) *) {if (dp[i][j - 2] 1 //a ab*|| (dp[i - 1][j] 1 s.charAt(i - 1) p.charAt(j - 2)) // abb ab*|| (dp[i - 1][j] 1 p.charAt(j - 2) .) // abb a.*) dp[i][j] 1;} else {if ((dp[i - 1][j - 1] 1 p.charAt(j - 1) .) // ab a.|| (dp[i - 1][j - 1] 1 p.charAt(j - 1) s.charAt(i - 1)) //ab ab) dp[i][j] 1;}}}return dp[m - 1][n - 1] 1;}
}
推荐
如果你对本系列的其他题目感兴趣可以参考华为OD机试真题及题解JAVA查看当前专栏更新的所有题目。
