[面試考題] 不重複

考題: 實作一個演算法來判斷一個字串中的字元是否不重複. 如果不能使用其他資料結構怎麼辦?

思維:假設字元有128個, 每一個都有特殊的數字, 因此~

1 造一個布林陣列

2 跑迴圈, 當遇到新的字元數字, 布林陣列[數字] 改為true

3 下一次再來, 如果發現其布林陣列[數字]為true , 代表該字元已經出現過了,

然後整個function就要回傳false

public static void main(String[] args) {
    System.out.println(isUniqueChars("abbs"));
}

static boolean isUniqueChars(String str) {
    if(str.length() > 128) return false;

    boolean[]char_set = new boolean[128];

    for(int i =0 ; i < str.length() ; i++) {
        int val =str.charAt(i);
        System.out.println(val);
        if(char_set[val]) {
            return false;
        }
        char_set[val]=true;
    }
    return true;

}