一个题目。。
给定两个字符串如果字符串中的字符出现的次数相同，则认为两字符串相等。
如“aab”和“aba”相等。
如何高效的实现。
[解决办法]
最起码要遍历这两个字符串吧，O（n），这一步骤可以声明两个长度为255的数组，盛放这些字母的出现次数，然后看一下这两个数组的内容。想不起来更高效的了。
[解决办法]
int i=0,j=0,k;
boolean same = false;
String a = new String("aaab");
String b = new String("baaa");
for(k=(int)'a';k<=(int)'z';k++)
{
i=0;
while(i<a.length)
{
if((int)a[i] == k)
{
i++;
}
}
j=0;
while(j<b.length)
{
if((int)b[j] == k)
{
j++;
}
}
if(i == j)
{
same =true;
break;
}
}
if(same)
{
System.out.println("same");
}
一种思路
[解决办法]
public static void main(String[] args) { String s1 = "bbb"; String s2 = "aba"; if (f(s1).equals(f(s2))) { System.out.println("相等"); } else { System.out.println("不相等"); } } static Map f(String s) { Map m = new HashMap(); char c; int con; for (int i = 0; i < s.length(); i++) { c = s.charAt(i); con = null == m.get(s) ? 0 : (Integer)m.get(s); m.put(s.charAt(i), con + 1); } return m; }
[解决办法]
从字符串中取出第i个字符用indexOf(i)，时间复杂应该为O(1);
设两个HashMap<Charactor,Integer>,key为字符，value为重复次数，就可以了。
下来比较两个HashMap。
如果两个HashMap的size()不相同，两个字符串不同，算法结束。
否则，把一个HashMap中的每key和value取出，在另一个HashMap中查找，并比较两者的value值就可以了。
综合起来，用HashMap来实现，时间复杂度为O(n)。n为字符串的长度。
[解决办法]
有时字符串匹配 可以考虑马尔可夫模型
[解决办法]
相同级别的算法之间,效率也是有差别的。
比如：同为O（n*log(n)）级别的排序算法有:快排，堆排，归并。但快排的效率一般的情况下高于另外的两种。
[解决办法]
public static boolean isStringsEquals(String s1, String s2) {
char[] arr1 = s1.toCharArray();
char[] arr2 = s1.toCharArray();
Arrays.sort(arr1);
Arrays.sort(arr2);
return Arrays.equals(arr1, arr2);
}
/**
* @param args
*/
public static void main(String[] args) {
String s1 = "aaab";
String s2 = "abaa";
if (isStringsEquals(s1, s2)) {
System.out.println(s1 + " = " + s2);
}
else {
System.out.println(s1 + " != " + s2);
}
}
[解决办法]
学习。。。。。
[解决办法]
学习。。。。。
[解决办法]
如果用N个素数的乘积怎么样？也就是从a-z每个用一个素数来取代，这样乘积相同的话就可以了，这样的话也是O(N),不过应该要更有效率一点
[解决办法]
只有ascii码的情况
public class TestStringEqual { public static void main(String[] args) { System.out.println( isEqual( "bcbb", "cbbb" ) ); } public static boolean isEqual( String a, String b ) { if( a.length() != b.length() ) return false; int[] aChances = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; int[] bChances = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; char []aChars = a.toCharArray(); char []bChars = b.toCharArray(); for( int i = 0; i < aChars.length; i++ ) { aChances[aChars[i]-'a']++; bChances[bChars[i]-'a']++; } return Arrays.equals(aChances, bChances); } }
[解决办法]
我觉得先第一步先判断长度，长度相等再下午下一步的判断。
[解决办法]
学习！
[解决办法]
String.toCharArray();
Arrays.sort();
equals();
[解决办法]
String a = "我不爱?"; String b = "不爱我?"; char [] one = a.toCharArray(); char [] tow = b.toCharArray(); Arrays.sort(one); Arrays.sort(tow); if (String.valueOf(one).equals(String.valueOf(tow))) { System.out.println(true); }else { System.out.println(false); }
[解决办法]
学习
[解决办法]
学习了
[解决办法]
[解决办法]
排序不错的思路呀！
[解决办法]
public class C { public static void main(String[] args) { String str = "aab"; String str2 = "aba"; System.out.println(equ(str,str2)); } public static boolean equ(String str,String str2){ boolean flag = true; if (str.length() == str2.length()) { while (!"".equals(str)) { String c=str.substring(0,1); //截取某个字符串的第一字符 String tempStr=str.replace(c,""); //用空串替换截取到的字符, String tempStr2 = str2.replace(c, ""); str2 = tempStr2; str = tempStr; if(str.length() != str2.length()){ //然后比较这两个字符串的长度 flag = false; } } } return flag; }}
[解决办法]
补充一点
public static boolean equ(String str,String str2){ boolean flag = true; if (str.length() == str2.length()) { while (!"".equals(str)) { String c=str.substring(0,1); //截取某个字符串的第一字符 String tempStr=str.replace(c,""); //用空串替换截取到的字符, String tempStr2 = str2.replace(c, ""); str2 = tempStr2; str = tempStr; if(str.length() != str2.length()){ //然后比较这两个字符串的长度 flag = false; [color=#FF0000]break;[/color] //加上这句可能速度会快点 } } } return flag; }
[解决办法]
代码还有个问题，两个字符串长度不相等的情况..楼主看的时候留意下
[解决办法]
用正则表达式
String st = "aab";
String stg = "aba";
if (st.matches("[aab]{3}")) {
if (stg.matches("[aab]{3}") {
System.out.println("Equals :" + st + " = " + stg);
}
}
[解决办法]
正则表达式可以解决吧
[解决办法]
先用equals方法?
然后判断长度?
再将字符串拆分一一对比?
学习中...
[解决办法]
UP
[解决办法]
上面的map做法才是正解
只要读一遍写一遍,时间O(n)