두 문자열 서로 permutation matching 인지 판별 문제

gistfile1.txt

/*
Question : Given two strings, write a method to decide if one is a permutation of the other.

가정:
문자열은 아스키코드로 구성
extra memory 사용가능.

해법: 
간단한 인덱스테이블을 생성 0으로 초기화 
첫번째 문자열의 아스키코드를 인덱스로 사용하여(0~126) 인덱스 테이블에 저장할때마다 해당 인덱스의 value ++1 씩 증가.
두번째 문자열의 아스키코드를 마찬가지로 인덱스로 활용, 저장할때마다 --1씩 감소.
감소 연산 후 해당 인덱스의 value < 0일때 return false;
인덱스 테이블을 0->128까지 검사, 모두 0이면 두 문자열은 서로 순열set 중의 1개 이므로 return true;

time complexity:
문자열의 길이가 n일때: O(2n+128)->O(n)
*/

int rangeException = 0;

bool checkPermutation(const char s1[], const char s2[]) {
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    char indexTable[128];
   
    if(len1 != len2) return false;
    if(len1 == 0 || len2 == 0) return false;
   
    memset(indexTable, 0, sizeof(indexTable));
   
    for(int i=0; i<len1 ; i++) {
        int temp = (int)s1[i];
        if(temp > 126) throw rangeException;
        indexTable[temp]++;
    }
   
    for(int i=0; i<len2 ; i++) {
        int temp = (int)s2[i];
        if(temp > 126) throw rangeException;
        indexTable[temp]--;
    }
   
    for(int i=0; i<128; i++) {
        if(indexTable[i] != 0) return false;
    }
   
    return true;
}

메모리를 아끼기 위해 문자열이 오직 알파벳이라 가정한다면 인덱스 테이블로, char indexTable[128] 대신에 int bitVector = 0(32bit) 을 이용하여 1<<index 연산을 활용할 수도 있을 것 같습니다.

가장 간단하게 풀면 이렇게 가능할 것 같습니다.

bool checkPermutation(const char s1[], const char s2[]) {
    string str1 = s1;
    string str2 = s2;

    sort(str1.begin(), str1.end());
    sort(str2.begin(), str2.end());

    return str1 == str2;
} 

중요한 내용은 아니지만 개인적으로는 함수 이름을 isPermutation으로 할 것 같아요.
그리고 exception은 throw std::out_of_range("non-ASCII code found");
그리고 temp > 126은 잘못된 것 같네요.
char의 범위가 -128 ~ 127까지 이기 때문에 오히려 < 0 체크가 더 맞을 지도...
strlen() 2번도 계산하면 O(2n+128)가 아니라 O(4n+128)이 더 맞을 수 있을 것 같네요.
-이병호

어..저건 제가 코드에서 의도를 제대로 드러내지 못한것 같은데, 문자열입력을 아스키코드라 가정했기 때문에, 아스키코드 테이블 크기가 0~126까지 이기 때문에 temp>126 을 error condition으로 지정했습니다. 지적하신대로 문자열 자체의 범위 에러 체크도 주어야 맞겠네요. 그리고 exception처리시 직접 에러 유형의 정의하지말고 std나 있는 정의 쓰라고 저번에도 지적해주셨는데..좀 찾아보고 앞으로는 그렇게 해야겠네요 두분다 감사합니다.

저도 C++을 잘을 모르지만 custom exception을 정의하려고 해도 std::exception를 상속해서 하는게 맞지 않나 싶은데요. 한 번 관련해서 찾아보시는 것이 좋을 듯...
그런데 여기는 comment에 대해서 notification기능이 없는게 약간 아쉽네요.