### Anagramic squares题号：98 难度： 35 中英对照

By replacing each of the letters in the word CARE with 1, 2, 9, and 6 respectively, we form a square number: 1296 = 362. What is remarkable is that, by using the same digital substitutions, the anagram, RACE, also forms a square number: 9216 = 962. We shall call CARE (and RACE) a square anagram word pair and specify further that leading zeroes are not permitted, neither may a different letter have the same digital value as another letter.

Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, find all the square anagram word pairs (a palindromic word is NOT considered to be an anagram of itself).

What is the largest square number formed by any member of such a pair?

NOTE: All anagrams formed must be contained in the given text file.

### Code

import java.io.BufferedReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;

public final class p98 {
public static void main(String[] args) {
long start=System.nanoTime();
String result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}
static public String run(){
String fileName="p098_words.txt";
HashMap<Integer,ArrayList<String>> words=new HashMap<Integer,ArrayList<String>>();
String line;
String tmp[]=line.split(",");
for(String s:tmp){
String ss=s.substring(1,s.length()-1);
if(words.containsKey(ss.length()))
else{
ArrayList<String> t=new ArrayList<String>();
words.put(ss.length(),t);
}
}
}
}catch(IOException e){
e.printStackTrace();
return null;
}
int ans=0;
//找出相同字母的单词对a和b
for(HashMap.Entry<Integer,ArrayList<String>> t:words.entrySet()){
ArrayList<String> list=t.getValue();
for(int i=0;i<list.size();i++) for(int j=i+1;j<list.size();j++){
String a=list.get(i);
String b=list.get(j);
//判断a和b是不是相同字母组成
if(!a.equals(b) && check(a,b)){
//具体计算
int res=dowith(a,b);
if(ans<res)
ans=res;
}
}
}
return Integer.toString(ans);
}
static public final boolean check(String a,String b){
int cnt[]=new int;
for(int i=0;i<a.length();i++){
cnt[a.charAt(i)-'A']++;
cnt[b.charAt(i)-'A']--;
}
for(int i=0;i<26;i++) if(cnt[i]!=0) return false;
return true;
}
static public final int dowith(String a,String b){
int n=a.length();
int ans=0;
for(int i=1;;i++){
int x=i*i;
int wx=weishu(x);
if(wx<n) continue;
if(wx>n) break;
//现在x是一个完全平方数，而且位数恰好为n
int[] xx=weishu2(x);
int[] f=new int;
for(int j=0;j<26;j++) f[j]=-1;
boolean vis[]=new boolean;//记录0-9有没有被对应
for(int j=0;j<10;j++) vis[j]=false;

boolean ok=true;
for(int j=0;j<n&&ok;j++){
if(f[a.charAt(j)-'A']<0)
f[a.charAt(j)-'A']=xx[j];
else if(f[a.charAt(j)-'A']!=xx[j])
ok=false;//该字符被对应到不同的数字了
if(vis[xx[j]])
ok=false;//数字xx[j]已经被对应过了
else vis[xx[j]]=true;
}
if(ok==false)
continue;//对应关系不正确
//对应完毕，映射关系是数组f
int y=0;
for(int j=0;j<n;j++){
y*=10;
y+=f[b.charAt(j)-'A'];
}
//y是b对应的数字，判断是否有前导零以及是否为完全平方数
if(weishu(y)!=n)
continue;
int ty=(int)Math.sqrt(y);
if(ty*ty!=y)
continue;//不是完全平方数
//是完全平方数，加入答案
ans=Math.max(ans,Math.max(x, y));
}
return ans;
}
//计算一个数的十进制位数
static public final int weishu(int a){
int res=0;
while(a!=0){
a/=10;
res++;
}
return res;
}
static public final int[] weishu2(int a){
int n=weishu(a);
int res[]=new int[n];
for(int i=0;i<n;i++){
res[i]=a%10;
a/=10;
}
//reverse res[]
for(int i=0;i*2<n;i++){
int x=res[i];
res[i]=res[n-1-i];
res[n-1-i]=x;
}
return res;
}
}
18769
59ms