Skip to content

leet code

1160 - Add Binary

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<algorithm>

using namespace std;

class Solution {
public:
    string addBinary(string a, string b) {
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());

        string result;
        int is_a_longer = a.size() > b.size();
        int min_len = is_a_longer?b.size():a.size();
        int max_len = is_a_longer?a.size():b.size();
        int flag=0;
        for(int i=0; i<min_len; ++i)
        {
            int next_val = a[i]+b[i] - 0x60 + flag;
            if(next_val > 1)
            {
                result += '0' + next_val - 2;
                flag = 1;
            }else
            {
                result += '0' + next_val;
                flag = 0;
            }
        }
        if(is_a_longer)
        {
            for(int i=min_len; i<max_len; ++i)
            {
                int next_val = a[i] - 0x30 + flag;
                if(next_val > 1)
                {
                    result += '0' + next_val - 2;
                    flag = 1;
                }else
                {
                    result += '0' + next_val;
                    flag = 0;
                }
            }
        }else
        {
            for(int i=min_len; i<max_len; ++i)
            {
                int next_val = b[i] - 0x30 + flag;
                if(next_val > 1)
                {
                    result += '0' + next_val - 2;
                    flag = 1;
                }else
                {
                    result += '0' + next_val;
                    flag = 0;
                }
            }
        }
        if(flag)
            result += "1";

        reverse(result.begin(), result.end());

        return result;
    }
};

1161 - Implement Strstr()

brute force 방법으로 푸니까 풀리긴 했는데, 탐색 시간이 꽤 길었습니다.

간단한 라빈카프 구현으로 다시 풀었습니다.

948ms => 4ms

약 200배 빨라졌습니다.

라빈카프 알고리즘은 haystack에서 needle을 찾을 때

haystack[i:i+needle]만큼의 구간을 hash화 하면서 끝까지 이동합니다.

hash를 만들면서 이동하기 때문에 O(1)만에 문자열 비교를 할 수 있습니다.

다만, hash collision이 일어날 수 있기 때문에 그 경우에는 확인을 해줘야 합니다.

가장 단순하게 문자열들을 더한 형태를 hash로 써도 충분히 빠르고 성능이 좋았습니다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int strStr(string haystack, string needle) {
        int idx = -1;
        int haySize = haystack.size();
        int needleSize = needle.size();
        for(int i=0; i< haySize - needleSize+1; ++i)
        {
            bool isFound = true;
            for(int j=i; j<i+needleSize; ++j)
            {
                if(haystack[j] != needle[j-i])
                {
                    isFound = false;
                    break;
                }
            }
            if(isFound)
            {
                idx = i;
                return idx;
            }
        }

        return idx;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
    int strStr(string haystack, string needle) {
        int hayLen = haystack.size();
        int needleLen = needle.size();
        int mod = needleLen > 12?4096:(1<<needleLen);
        if(needle == "") return 0;
        if(needleLen == 0) return -1; // base condition 1
        if(needleLen > hayLen) return -1; // base condition 2

        // calculate needleHash
        int needleHash = 0;
        for(int i=0; i<needleLen; ++i)
        {
            needleHash = (needleHash*2 + needle[i]) % mod;
        }
        //printf("needlehash: %d\n", needleHash);

        // search
        int hayHash = 0;
        for(int i=0; i<needleLen; ++i)
        {
            hayHash = (hayHash*2 + haystack[i]) % mod;
        }
        //printf("hayhash: %d\n", hayHash);
        if(hayHash == needleHash)
        {
            if(check(haystack, needle, 0)) return 0;
        }

        for(int i=1; i<hayLen-needleLen+1; ++i)
        {
            hayHash = (hayHash*2 + haystack[i+needleLen-1]) % mod;
            //printf("hayhash: %d\n", hayHash);
            if(hayHash == needleHash)
            {
                if(check(haystack, needle, i)) return i;
            }
        }
        return -1;
    }

    bool check(string& hay, string& needle, int hayIdx)
    {
        for(int i=0; i<needle.size(); ++i)
        {
            if(hay[hayIdx+i] != needle[i]) return false;
        }
        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool cmp(string a, string b, int i){
        for(int j=0; j<b.size(); j++){
            if(a[i+j]!=b[j]){return false;}
        }
        return true;
    }
    int strStr(string haystack, string needle) {
        int h_size=haystack.size(), n_size=needle.size(), h=0, n=0;
        if(h_size<n_size){return -1;}
        for(int i=0; i<n_size; i++){h+=haystack[i]; n+=needle[i];}
        for(int i=0; i<h_size-n_size+1; i++){
            if(h==n and cmp(haystack, needle, i)){return i;}
            if(i<h_size-n_size){h+=haystack[i+n_size]-haystack[i];}
        }
        return -1;
    }
};