学步园

问题描述：

String 1: ABCDEFGHLMNOPQRS

String 2: DCGSRQPO
答案是true，所有在string2里的字母string1也都有。
  
如果是下面两个字符串：  
String 1: ABCDEFGHLMNOPQRS   
String 2: DCGSRQPZ  

答案是false，因为第二个字符串里的Z字母不在第一个字符串里。

此方法为暴力破解  时间复杂度O(M*N)
public class Main {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
    String str1="ABCDEFGHLMNOPQRS";  
   String str2="DFHA";

   int N=str1.length();
   int M=str2.length();
   int[] arr1 = new int[N];
   int[] arr2 = new int[M];

for(int i=0;i<N;i++){
arr1[i] = str1.charAt(i)-'A';
}
for(int j=0;j<M;j++){
arr2[j] = str2.charAt(j)-'A';
}
int num=0;
for(int k=0;k<M;k++){
for(int m=0;m<N;m++){
if(arr2[k]==arr1[m]){
num++;
break;
}
}
}
if(num==M){
System.err.println("Right!");
}
else {
System.err.println("Wrong!");
} 
}
}

利用质数  时间复杂度是O(M+N) 缺点是乘积有可能溢出
public class Main1 {


/**
* @param args
*/
public static void main(String[] args) {

String str1 = "ABCDEFGOPQ";  
   String str2 = "GFR";
   int N = str1.length();
   int M = str2.length();
   int[] arr1 = new int[N];
int[] arr2 = new int[M]; 
int Numbers[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,  
                61, 67, 71, 73, 79, 83, 89, 97, 101};

double sum=1;
int count=0;
for(int i=0;i<N;i++){
int index1 = str1.charAt(i)-'A';
arr1[i] = Numbers[index1];
sum *= arr1[i];
}
System.err.println(sum);
for(int j=0;j<M;j++){
int index2 = str2.charAt(j)-'A';
arr2[j] = Numbers[index2];
if(sum % arr2[j]==0){
count++;
}
}
if(count==M){
System.out.println("Right!");
}
else {
System.out.println("Wrong!");
}
}


}