全排列、回溯-易彰彪的一张biao

- 日理万妓 2023-07-24 08:18 43阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70]  
**样例输入**

5 5
    yiZha
    nGBia
    oaerg
    htyfj
    awert
    yizhangbiao

**样例输出**

YES

import java.util.Scanner;
    
    public class Main{
        
        static int n=0;
        static String ss="";
        static String s1="";
        private static void dfs(String[] arr , int nn) {
        
            int length = arr.length;
            ss+=arr[nn].toLowerCase();
            if (ss.contains(s1.toLowerCase())){
        
                System.out.println("YES");
                System.out.println(ss);
                System.exit(0);
            }
    
            if(nn>=length-1) {
        
                ss="";
                return;
            }else {
        
                for(int i=nn;i<length;i++) {
        
                    {
        String temp = arr[nn]; arr[nn] = arr[i]; arr[i] = temp;}
                    dfs(arr,nn+1);
                    {
        String temp = arr[nn]; arr[nn] = arr[i]; arr[i] = temp;}
                }
            }
        }
    
        public static void main(String[] args) {
        
            Scanner scanner=new Scanner(System.in);
            while (scanner.hasNextInt()){
        
                n=scanner.nextInt();
                int m=scanner.nextInt();
                String [] s=new String[n+1];
                for (int i = 1; i <=n ; i++) {
        
                    s[i]=scanner.next();
                }
                s1=scanner.next();
                dfs(s,1);
                System.out.println("NO");
            }
    
        }
    
    }

import java.util.Scanner;
    
    public class Main {
        
        static char[] str=new char[50];
    //    static char[] s=new char[50];
        static char[] tar=new char[1000];
    
        static int len1=0;
        static int len2=0;
        public static int se(char s[],char ms[]){
        
            int i=0;
            int j=0;
            while (i<len1&&j<len2){
        
                if(s[i]==ms[j] || s[i]-ms[j]==32 ||s[i]-ms[j]==-32)
                {
        
                    ++i;
                    ++j;
                }
                else
                {
        
                    i=i-j+1;//回溯关键
                    j=0;
                }
            }
            if(j>=len2) return 1;
            else return -1;
    
    
        }
        public static void main(String[] args) {
        
            Scanner scanner=new Scanner(System.in);
            while (scanner.hasNextInt()){
        
                int n=scanner.nextInt();
                int m=scanner.nextInt();
                String str1="";
                for (int i = 0; i <n ; i++) {
        
                    str1+=scanner.next();
                }
                str=str1.toCharArray();
                String tars=scanner.next();
                tar=tars.toCharArray();
                len1=m*n;
                len2=tars.length();
                if (len2>len1){
        
                    System.out.println("NO");
                    continue;
                }
                int flag=se(str,tar);
    
                if(flag==1)
                    System.out.println("YES");
                else System.out.println("NO");
    
            }
    
        }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70]: /images/20230528/b984e1a47dd345ebb73389e0f2430c6e.png