배열과 문자열

중복이 없는가: 문자열이 주어졌을 때, 이 문자열에 같은 문자가 중복되어 등장하는지 확인하는 알고리즘을 작성하라. 자료구조를 추가로 사용하지 않고 풀 수 있는 알고리즘 또한 고민하라.

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);
        if (char_set[val]) {
            if(char_set[val])
                return false;
        }
        char_set[val] = true;
    }
    return true;
}

1.2 순열 확인 : 문자열 두 개가 주어졌을 때 이 둘이 서로 순열 관계에 있는지 확인하라

풀이 #1 : 정렬하라
public String sort(String s) {
    char[] content = s.toCharArray();
    java.util.Arrays.sort(content);
    return String.valueOf(content);
}

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

풀이 #2 문자열에 포함된 문자의 출현 횟수가 같은지 검사하기
booelan permutation(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    
    int[] letters = new int[128]; // 문자 집합의 크기는 다를 수 있다.
    
    char[] s_array = s.toCharArray();
    for (char c : s_array) { // s 내에서 각 문자의 출현 횟수를 센다.
        Letters[c]++;
    }
    
    for (int i = 0; i < t.length(); i++) {
        int c = (int) t.charAt(i);
        letters[c]--;
        if (letters[c] < 0) {
            return false;
        }
        
    }
    return true;
}

1.3 회문 순열 : 주어진 문자열이 회문의 순열인지 아닌지 확인하는 함수. 회문이란 앞으로 읽으나 뒤로 읽으나 같은 단어 혹은 구절을 의미하며, 순열이란 문자열을 재배치하는 것을 뜻한다.