判断字符串是否唯一？

• 判断字符串是否唯一？

实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

``` 示例 1： 输入: s = "abcdeff" 输出: false

示例 2： 输入: s = "abc" 输出: true ```

思路1：根据字符集大小定义一个合理的数组arr例如，ASCII 256，定义个256大小的数组，遍历字符串s，设置s[i]++，最后统计arr长度，跟s的长度对比，一样则返回true，否则返回false。时间复杂度O(n);空间复杂度O(n)

思路1本质上是使用hashmap这种数据结构来计算一个字符串是否重复，PHP数组即可实现，是不是很方便 思路1缺点：需要遍历整个字符串，例如aabcdef，不能在s[1]就发现重复，返回

PHP语言实现

```PHP //PHP语言实现 class Solution {

/**
 * @param String $astr
 * @return Boolean
 */
function isUnique($astr) {
    $temp=[];
    $lenth=strlen($astr);
    for($i=0;$i<$lenth;$i++){
        if(isset($temp[$astr[$i]])){
            $temp[$astr[$i]]++;
        }else{
            $temp[$astr[$i]]=1;
        }
    }
    $count=count($temp);
    if($count==$lenth){
        return true;
    }else{
        return false;
    }
}   

} ```

思路1改进版PHP

```PHP //PHP语言实现 class Solution {

/**
 * @param String $astr
 * @return Boolean
 */
function isUnique($astr) {
    $temp=[];
    $lenth=strlen($astr);
    for($i=0;$i<$lenth;$i++){
        if(isset($temp[$astr[$i]])){
           return false;
        }else{
            $temp[$astr[$i]]= true;
        }
    }
    return true;
}   

} ```

Golang实现

Go //GO语言实现 //使用map，类似PHP的key value数组 func isUnique(astr string) bool { var arrMap map[string]bool arrMap = make(map[string]bool) for i := 0; i < len(astr); i++ { if arrMap[string(astr[i])] { return false } arrMap[string(astr[i])] = true } //for k,v := range arrMap{ // fmt.Println(k,v) //} return true }

如果字符集在ASCII码，则可以使用一个256大小的bool数组来实现

```Go //GO语言实现 //使用切片数组 func isUnique(astr string) bool { strLen := len(astr) var arr []bool = make([]bool, 256)

for i := 0; i < strLen; i++ {
    if arr[astr[i]] == true {
        return false
    }
    arr[astr[i]] = true
}
return true

}

```

还有一种节省空间的使用方法，通过位运算来实现

例如ASCII字符可以使用一个长度为8的int数组arr[8]来表示(先不考虑arr[0])（int 4个字节，共32位二进制，通过二进制上的0、1表示一个数是否存在） 例如字符b对应的ASCII码是98,98/32=3;98%32=2;可以用arr[3]所在整数对应的二进制的第2位来表示

```Go //GO语言实现 //使用位运算，减少空间使用 func isUnique(astr string) bool { strLen := len(astr) var arr = make([]int, 8) for i := 0; i < strLen; i++ { var idx int = int(astr[i] / 32) var shift int = int(astr[i] % 32) if (arr[idx] & (1 << shift)) != 0 { return false } arr[idx] |= 1 << shift } return true }

```

赞0 2993次