判断字符串是否没有重复元素

题意

实现一个算法确定字符串中的字符是否均唯一出现

样例

给出 "abc",返回 true

给出 "aab",返回 false

思路

解法一:可以利用查表法,首先建立一个大小为 256 位的布尔类型的数组,因为 ASCII 表中一共就有 256 的字符,依次取字符串中的每一个位,将其在 ASCII 表中的位置放到数组中,True 表示该字符已存在,Flase 则表示该字符不存在。

解法二:不利用额外空间的话,就将当前位与剩余位依次进行比较才能实现,比较消耗时间。

代码实现

解法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
/**
* @param str: a string
* @return: a boolean
*/
public boolean isUnique(String str) {
if (str == null)
return false;

boolean[] char_set = new boolean[256];
for (int i = 0; i < str.length(); i++) {
int var = str.charAt(i);
if (char_set[var])
return false;
char_set[var] = true;
}

return true;
}
}

解法二:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
/**
* @param str: a string
* @return: a boolean
*/
public boolean isUnique(String str) {
if (str == null || str.length() == 0)
return false;

for (int i = 0; i < str.length(); i++) {
for (int j = i + 1; j < str.length(); j++) {
if (str.charAt(i) == str.charAt(j))
return false;
}
}

return true;
}
}

原题地址

LintCode:判断字符串是否没有重复字符