Google 面试第一题解法

Solve this cryptic equation, realizing of course that values for M and E could be interchanged. No leading zeros are allowed.

WWWDOT - GOOGLE = DOTCOM

思路：
穷举法，式子中共有9个不同的字母，数字0－9有10个，因此就从10个数字中任取9个，排成一列，这样分别对应了式子中的字母。
然后判断当前取出的这9个数，是否满足条件。本程序中用check2 函数判断，另外需要考虑WE是可以互换，但不可以相同

答案：只有两组解
777589 - 188103 = 589486
777589 - 188106 = 589483

程序：
Perm1.java
package org.chao.perm;

public class Perm1 {
public static void main(String[] args) {
int size = 9;
int[] a = new int[size];
int all = 10;
check(a,all,size,0);
}

private static void check(int[] a, int all, int size, int depth) {
if(size == depth){
check2(a);
}
for(int i=0; i<all; i++){
int j = 0;
for(;j<depth;j++){
if(a[j] == i){
break;
}
}
if(j==depth && depth<size){
a[depth]=i;
check(a,all, size,depth+1);
}
}
}

private static void check2(int[] a) {
//WWWDOT - GOOGLE = DOTCOM
//w0/6 d1 o2 t3 g4 l5 e6/0 c7 m8
int s1 = a[0]*111000+a[1]*100+a[2]*10+a[3];
int s2 = a[4]*100100+a[2]*11000+a[5]*10+a[6];
int s3 = a[1]*100000+a[2]*10010+a[3]*1000+a[7]*100+a[8];
if(s1-s2 == s3){
System.out.println(s1+" - "+s2+" = "+s3);
}
s1 = a[6]*111000+a[1]*100+a[3]*10+a[4];
s2 = a[4]*100100+a[2]*11000+a[5]*10+a[0];
s3 = a[1]*100000+a[2]*10010+a[3]*1000+a[7]*100+a[8];
if(s1-s2 == s3){
System.out.println(s1+" - "+s2+" = "+s3);
}
}
}


对上面程序的一点改进：
改进部分：如何从10个数字中取出9个排成一列
上面例子中每次递归都要做depth判断来排除已经选用的数字
下面这个程序则不需要判断

程序：
Perm2.java
package org.chao.perm;
public class Perm2 {
public static void main(String[] args) {
int num[] = { 0,1,2,3,4,5,6,7,8,9 };
int n=num.length;
generate(num, n-1);
}
private static void generate(int[] num, int n) {
if (n == 0) {
//打印出num;
} else {
for (int i = 0; i <= n; i++) {
swap(num,i,n-1);
generate(num, n - 1);
swap(num,i,n-1);
}
}
}
private static void swap(int[] num, int i, int j) {
int tmp = num[i];
num[i] = num[j];
num[j] = tmp;
}
}