请实现一个算法,确定一个字符串的所有字符是否全都不同。这里我们要求不允许使用额外的存储结构。
给定一个string iniString,请返回一个bool值,True代表所有字符全都不同,False代表存在相同的字符。保证字符串中的字符为ASCII字符。字符串的长度小于等于3000。
APPROACH1 SET
CC150没有必须要求不许用额外存储。
如果用存储,可以问一下,字符集是ASCII还是UNICODE。ASCII的长度只有256,新建一个长度256的boolean数组就行了。大于256可以直接返回false。时间O(n)。
APPROACH2 BRUTE FORCE
O(n2) 。
public boolean checkDifferent(String iniString) {
// write code here
for(int i = 0 ; i < iniString.length()-1 ; i ++)
for(int j = i + 1 ; j < iniString.length() ; j ++){
if(iniString.charAt(i) == iniString.charAt(j)){
return false;
}
}
return true;
}
APPROACH3 SORT
排序,但是也要额外存储。
--