题目:
原文:
Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures?
译文:
实现一个算法判断一个字符串中的字符是否唯一的,不能使用额外的数据结构。
解答:
思路:首先应该思考构成字符串的字符集有多大,单是26个字母还是ascii集,或更大的字符集?对于不同的字符集,对应不同的解法。
为了简单,假设字符集为ascii,可以开一个大小为256的bool数组来表征每个字 符的出现。数组初始化为false,遍历一遍字符串中的字符,当bool数组对应位置的值为真, 表明该字符在之前已经出现过,即可得出该字符串中有重复字符。否则将该位置的bool数组 值置为true。代码如下:
该算法的时间复杂度为O(n),长度为n的字符串的空间复杂度为O(n);
public static boolean isUniqueChars0(String str){
boolean[] char_set=new boolean[256];
for(int i=0;i<str.length();i++){
int val=str.charAt(i);
if(char_set[val]) return false;
char_set[val]=true;
}
return true;
}
若字符集是a-z(A-Z),用位运算比较省空间:
public static boolean isUniqueChars2(String str){
int checker=0;
for(int i=0;i<str.length();++i){
int val=str.charAt(i)-'a';
if((checker&(1<<val))>0) return false;
checker|=(1<<val);
}
return true;
}
完整代码如下:
class Q1_1{ public static void main(String[] arg){ String s1="i am navy."; String s2="abcdefghijklmnopqstuvwxyzABCDEF1234567890"; System.out.println(isUniqueChars0(s1)); System.out.println(isUniqueChars0(s2)); //System.out.println(isUniqueChars2(s1)); //System.out.println(isUniqueChars2(s2)); } public static boolean isUniqueChars0(String str){ boolean[] char_set=new boolean[256]; for(int i=0;i<str.length();i++){ int val=str.charAt(i); if(char_set[val]) return false; char_set[val]=true; } return true; } //字符集只是a-z(或是A-Z) public static boolean isUniqueChars2(String str){ int checker=0; for(int i=0;i<str.length();++i){ int val=str.charAt(i)-'a'; if((checker&(1<<val))>0) return false; checker|=(1<<val); } return true; } }
此题还有很多其他方法,如有更好,还望指教!