[面試考題] 檢查變位字

考題: 給定兩個字串, 寫一個方法判斷一個是否是另一個的變位字

思維:造一個方法

1 先比較其長度是否相等

2 比較兩個值做順序排序, 內容是否會相等

順序排序:

a 產生一個字元char陣列

b使用Arrays.sort

c產生新的字串

public static void main(String[]args){
    System.out.println(permutation("see","ese"));
}
static String sort(String s){
    char[]content = s.toCharArray();
    java.util.Arrays.sort(content);
    return new String(content);
}

static boolean permutation(String s, String t){
    if(s.length()!=t.length()){
        return false;
    }
    return sort(s).equals(sort(t));
}

[面試考題] 不重複

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

思維:假設字元有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;

}