题目
有一个由字符组成的等式：WWWDOT - GOOGLE = DOTCOM，每个字符代表一个0～9之间的数字，WWWDOT、GOOGLE和DOTCOM都是合法的数字，不能以0开头。请找出一组字符和数字的对应关系，使它们互相替换，并且替换后的数字能够满足等式。
思路
据说这是Google公司的面试题，我没有考证过，不过这种字符方程（或字符等式）问题有很多变种，比如2005年的Google中国编程挑战赛第二轮淘汰赛有一道名为“SecretSum”的500分的竞赛题，与本题如出一辙，只不过字母是3个，而且用的是加法计算。这个问题其实并不难，你可以将其列成竖式减法的形态，然后人工推算出来，不过接下来我们要使用穷举法来求解这个问题。
从穷举法的角度看，这是一个典型的排列组合问题，题目中一种出现了9个字母，每个字母都可能是0～9之间的数字，穷举的方法就是对每个字母用0～9的数字尝试10次，如果某一次得到的字母和数字的对应关系能够满足减法等式，则输出这一组对应关系。根据题目意思，每个字母代表一个数字，也就是说，如果W代表1，则其他8个字母就不可能是1。很显然，这是个组合问题，如果不考虑0开头数字的情况，这样的组合应该有10×9×8×7×6×5×4×3×2=3628800种组合，在这样的数量级上使用穷举法，计算机处理起来应该没有压力。
现在考虑给出一种解决这种字符方程问题的通用解法。从数据结构定义上，首先要避免使用固定9个字符的方法，这就需要定义一个可变化的字符元素列表，每个字符元素包含3个属性，分别是字母本身、字母代表的数字以及是否是数字的最高位。
题解
代码语言：javascript复制public class Main {
public static void main(String[] args) {
f();
}
public static void f() {
int a1 = 10; int a2 = 100; int a3 = 1000; int a4 = 10000; int a5 = 100000;
for(int W=0;W<10;W ) {
for(int D=0;D<10;D ) {
for(int O=0;O<10;O ) {
for(int T=0;T<10;T ) {
for(int G=0;G<10;G ) {
for(int L=0;L<10;L ) {
for(int E=0;E<10;E ) {
for(int C=0;C<10;C ) {
for(int M=0;M<10;M ) {
int WWWDOT = W*a5 W*a4 W*a3 D*a2 O*a1 T;
int GOOGLE = G*a5 O*a4 O*a3 G*a2 L*a1 E;
int DOTCOM = D*a5 O*a4 T*a3 C*a2 O*a1 M;
if(W!=D && W!=O && W!=T && W!=G && W!=L && W!=E && W!=C && W!=M) {
if(D!=O && D!=T && D!=G && D!=L && D!=E && D!=C && D!=M) {
if(O!=T && O!=G && O!=L && O!=E && O!=C && O!=M) {
if(T!=G && T!=L && T!=E && T!=C && T!=M) {
if(G!=L && G!=E && G!=C && G!=M) {
if(L!=E && L!=C && L!=M) {
if(E!=C && E!=M) {
if(C!=M) {
if (WWWDOT - GOOGLE == DOTCOM) {
System.out.println(WWWDOT "-" GOOGLE "=" DOTCOM);
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}结果
