这道题是这样的,有两个字符串,比较他们中间的值是否相等.注意不是一般的相等!例如
String stra = "ccaaiub"
String strb = "iubacac"
如果出现这样的情况也是相等的!
也就是说两个字符串中字符的个数相等,每个字符出现的次数也是相等的,有什么好的解决方案,考虑下效率上面的因素,因为字符串是不定长的
[b]问题补充：[/b]
如果字符串中穿插的有其它字符,比如数字123等等!给点伪代码,大家都看看!
[code="java"]
import java.util.*;
public class StringCompare
{
/**
* TODO 方法说明
*
* @param args
*/
public static void main(String[] args)
{
// TODO Auto-generated method stub
String stra = "ccaaiub" ;
String strb = "iubacac" ;
System.out.println(compare(stra,strb));
}
public static boolean compare(String a, String b)
{
if(a == null && b == null)
return true;
if(a == null || b == null)
return false;
if(a.equals(b))
return true;
if(a.length() != b.length())
return false;
byte[] byteA = a.getBytes();
byte[] byteB = b.getBytes();
Map<Byte,Integer> mapA = new HashMap<Byte, Integer>();
Map<Byte,Integer> mapB = new HashMap<Byte, Integer>();
Byte btA,btB;
for(int i=0;i<byteA.length;i++)
{
btA = byteA[i];
btB = byteB[i];
if( mapA.get(btA) == null )
mapA.put(btA, 1);
else
mapA.put(btA, mapA.get(btA) + 1);
if( mapB.get(btB) == null )
mapB.put(btB, 1);
else
mapB.put(btB, mapB.get(btB) + 1);
}
if(mapA.equals(mapB))
return true;
else
return false;
}
}
[/code]
把两个字符串分别在串内排序，生成新对象后比较一下是否equals()
那怎么排序呢？ 把字符串变成字符数组，再把字符数组变成ArrayList，再用Collections.sort()排序
最后比较一下两个ArrayList是否equals()。
我的思路是假设字符串中只包含ASCII字符，那就只需要两个长为128的整形数组即可。
[code="java"]
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
System.out.println(compare("abcd", "cbaa"));
}
public static boolean compare(String str1, String str2) {
if (str1 == null || str2 == null) {
return true;
}
if (str1.length() != str2.length()) {
return false;
}
int[] v1 = new int[128];
int[] v2 = new int[128];
Arrays.fill(v1, 0);
Arrays.fill(v2, 0);
for (int i = 0; i < str1.length(); i++) {
v1[str1.charAt(i)]++;
}
for (int i = 0; i < str2.length(); i++) {
v2[str2.charAt(i)]++;
}
boolean equal = true;
for (int i = 0; i < v1.length; i++) {
if (v1[i] != v2[i]) {
equal = false;
break;
}
}
return equal;
}
}
[/code]
我是低水平 能想到的有两种, 一种是冒泡把字符串排列. 一种是楼上大哥那种比较对象.
代码写的有点乱基础判断那里想到什么就乱写上了.好像得修改修改.
[code="java"]
import java.util.HashMap;
import java.util.Map;
public class Test {
public static void main(String[] args) {
String a = "ccaaiub" ;
String b = "iubacac" ;
//方法一,比较对象
System.out.println(equ(a, b));
//方法二,排序比较
System.out.println(equ2(a, b));
}
private static boolean equ(String a , String b) {
boolean boo = a == b;
if (a == null || b == null)
return boo;
else
if (boo) return boo;
if (a .length() != b.length())
return false;
Map<Character, Integer> ma = new HashMap<Character, Integer>();
Map<Character, Integer> mb = new HashMap<Character, Integer>();
for (char c : a.toCharArray())
ma.put(c, ma.get(c) == null ? 1 : (ma.get(c) + 1));
for (char c : b.toCharArray())
mb.put(c, mb.get(c) == null ? 1 : (mb.get(c) + 1));
return ma.equals(mb);
}
private static boolean equ2(String a , String b) {
boolean boo = a == b;
if (a == null || b == null)
return boo;
else
if (boo) return boo;
if (a .length() != b.length())
return false;
a = sort(a);
b = sort(b);
return a.equals(b);
}
private static String sort (String str) {
char[] as = str.toCharArray();
for (int i = 0; i < as.length; i ++) {
for (int j = 0; j < as.length - i - 1; j ++) {
int a = as[j];
int b = as[j + 1];
if (a > b) {
a = a ^ b;
b = a ^ b;
a = a ^ b;
}
as[j] = (char) a;
as[j + 1] = (char) b;
}
}
return new String(as);
}
}
[/code]
没理解错的话，问题应该是说只要出现字符类型和数量同时相等，则视为相等。
可以考虑HashMap，key为字符，value为该字符出现次数。
按字符遍历第一个string。填充此map。出现多次则增加。
如上例子，处理结果为：
map={
'a' => 2
'b' => 1
'c' => 2
'u' => 1
'i' => 1
}
按字符遍历第二个string。出现一次减一次
遍历map，查看所有key对应的value是否都为0.0则说明相等
时间复杂度=O(3n),n为字符串长度
[code="java"]
public class TestStr {
public static void main(String[] args) {
String str1 = "aaabb11";
String str2 = "1a1abab";
System.out.println(euq(str1, str2));
}
public static boolean euq(String str1,String str2){
if(str1 == str2){
return true;
}
if(str1 == null || str2 == null){
return false;
}
if(str1.length() == str2.length()){
for (char c : str1.toCharArray()) {
int length = str2.length();
str2 = str2.replaceFirst(String.valueOf(c), ""); //每次把 str2 的一个字符替换掉
if(length == str2.length()){ //当长度不一样的话说明本次替换没有匹配的字符, 失败的替换
return false;
}
}
return true;
}
return false;
}
}
[/code]