确定一个字符串的所有字符全都不同算法实现

不念不忘少年蓝@ 2022-07-25 19:57 105阅读 0赞

首先要确认字符串的编码方式，是ASCII还是Unicode，这很重要。

我们就当是ASCII来处理吧，如果不是的话，只需要扩大存储空间就可以了，其余逻辑都是一样的。

**算法一：**  
算法的中心思想是利用散列表的原理，先初始化一个数组，然后循环取出字符，将下标为此字符的ASCII值的位置置为true，如果将要存储的下标已经是true，则证明有重复的字符了，返回false。

/** * 判断一个字符串是否各个字符都不同 * * @author liudezhi */
    public class StringIsRepeat { 
        public static void main(String[] args) {
            String str = "asdfghjkla";
            boolean resultFlag = isUniqueChars(str);
            System.out.println("结果为："+resultFlag);
        }
        /** * 全不相同返回true，有相同的返回false * @param str * @return */
        public static boolean isUniqueChars(String str) {
            if (str.length() > 256) {
                return false;
            }
            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;
        }
    }

这个算法的时间复杂度为O(n),其中n为字符串长度。空间复杂度为O(1)。

**算法二：**  
算法的中心思想是使用位向量，可以将空间占有减少为原来的1/8。因为boolean是一个字节，int是4个字节。

/** * 判断一个字符串是否各个字符都不同 * * @author Administrator */
    public class StringIsRepeat { 
        public static void main(String[] args) {
            String str = "asdfghjkl";
            resultFlag = isUniqueChars(str);
            System.out.println("结果为："+resultFlag);
        }
    
        /** * 全不相同返回true，有相同的返回false * @param str * @return */
        public static boolean isUniqueChars(String str){
            if(str.length() > 26) {
                return false;
            }
            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;
        }
    }