Hackerrank:夏洛克和字谜
Hackerrank: Sherlock and Anagrams
问题描述:https://www.hackerrank.com/challenges/sherlock-and-anagrams
添加问题陈述的快照:
我只有少数测试用例是正确的。我的算法是:
- 查找给定字符串的所有子字符串。
- 通过为每个字母表使用数组为每个子字符串创建代码。
- 将该代码转换为字符串并使用 hashmap 映射该字符串。
- 如果子字符串的映射值包含非零值,则增加结果。
我的代码:
static int sherlockAndAnagrams(String s) {
HashMap<String,Integer> map = new HashMap<String,Integer>();
int d,i,k=0;
int length = s.length();
int n = length*(length+1)/2;
String []sub = new String[n];
for (d = 0; d < length; d++){
for(i = d+1; i <= length; i++)
{
sub[k++] = s.substring(d, i);
}
}
int []c = new int[26];
int result=0;;
for(int l=0;l<n;l++){
for(int m=0;m<25;m++){
c[m] = 0;
}
char []suba = sub[l].toCharArray();
for(char ch : suba){
c[ch-'a']+=1;
}
String temp = Arrays.toString(c);
Integer x = map.get(temp);
if(x!=null){
result = result+x;
map.put(temp,++x);}
else{
map.put(temp,1);
}
}
return result;
}
好的,这里有几件事。
你必须数对,而不是碰撞了多少。
那么,就是result = result + x;
此外,map.put(...,x++)
应该是 map.put(...,++x);
,因为我们将使用预先增加的值进行更新。
此外,您填写的 c
从 0
到 24
但它应该是 0
到 25
。就此而言,只做 Arrays.fill(c,0)
是更好的做法。
为了space效率,我们完全可以避免将每个子数组都放在一个数组中,而只是根据字符对子数组进行排序。这样,每个 Anagram 都会映射到映射中的相同键,从而帮助您避免将每个数组显式存储在 sub
字符串数组中。但是,总体 space 复杂度将保持不变。
问题描述:https://www.hackerrank.com/challenges/sherlock-and-anagrams
添加问题陈述的快照:
我只有少数测试用例是正确的。我的算法是:
- 查找给定字符串的所有子字符串。
- 通过为每个字母表使用数组为每个子字符串创建代码。
- 将该代码转换为字符串并使用 hashmap 映射该字符串。
- 如果子字符串的映射值包含非零值,则增加结果。
我的代码:
static int sherlockAndAnagrams(String s) {
HashMap<String,Integer> map = new HashMap<String,Integer>();
int d,i,k=0;
int length = s.length();
int n = length*(length+1)/2;
String []sub = new String[n];
for (d = 0; d < length; d++){
for(i = d+1; i <= length; i++)
{
sub[k++] = s.substring(d, i);
}
}
int []c = new int[26];
int result=0;;
for(int l=0;l<n;l++){
for(int m=0;m<25;m++){
c[m] = 0;
}
char []suba = sub[l].toCharArray();
for(char ch : suba){
c[ch-'a']+=1;
}
String temp = Arrays.toString(c);
Integer x = map.get(temp);
if(x!=null){
result = result+x;
map.put(temp,++x);}
else{
map.put(temp,1);
}
}
return result;
}
好的,这里有几件事。
你必须数对,而不是碰撞了多少。
那么,就是
result = result + x;
此外,
map.put(...,x++)
应该是map.put(...,++x);
,因为我们将使用预先增加的值进行更新。此外,您填写的
c
从0
到24
但它应该是0
到25
。就此而言,只做Arrays.fill(c,0)
是更好的做法。
为了space效率,我们完全可以避免将每个子数组都放在一个数组中,而只是根据字符对子数组进行排序。这样,每个 Anagram 都会映射到映射中的相同键,从而帮助您避免将每个数组显式存储在 sub
字符串数组中。但是,总体 space 复杂度将保持不变。