[C++/LeetCode/Top Interview Questions]String

문제 1. Reverse String

class Solution {
public:
    void reverseString(vector<char>& s) {
        reverse(s.begin(), s.end());
    }
};

 

vector에는 reverse(start, end) 함수가 있으니까 사용하면 된다. 

 

문제 2. Reverse Integer

class Solution {
public:
    int reverse(int x) {
        string str_x = to_string(x);
        string rev_str_x;
        for (int i=str_x.size()-1; i>-1; i--) rev_str_x += str_x[i];
        
        long long res = stoll(rev_str_x);
        if (x < 0) res *= -1;
        return (res<INT_MIN || res>INT_MAX) ? 0 : res;
    }
};

 

stoi(), stol(), stoll()에 대해 알 수 있었다. stoi는 string to integer, stol은 string to long, stoll은 string to long long의 약자다. 예전에 파이썬에서 이진 검색 알고리즘을 공부하다가 자료형의 최댓값 부분을 인상깊게 본 적이 있다. 이진 검색 알고리즘에서 중간 값을 구할 때 보통 (left+right)//2 를 하는데 이렇게 하면 자료형이 최댓값을 초과해 overflow를 발생시키게 된다. 따라서 mid = left + (right - left) // 2 이렇게 구현해야 한다. 이 문제도 파이썬이었으면 정수 오버플로우 에러를 겪지 않았을거다. 

 

• 문자열 변수를 선언할 때는 string, 숫자 변수를 문자열로 바꿀때는 to_string()함수를 사용하면 된다.
• 문자열 더하기(+)를 허용한다.
• 정수 최대값, 최소값 INT_MAX, INT_MIN
• stoi(), stol(), stoll()

 

문제 3.  First Unique Character in a String

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char, int> dict;
        for (int i=0; i<s.size();i++){
            if (dict.count(s.at(i)) > 0) dict[s.at(i)] += 1;
            else dict.insert(make_pair(s.at(i), 1));
        }
        for (int i=0; i<s.size(); i++){
            if (dict[s.at(i)] == 1) return i;
        }
        return -1;
    }
};

 

unordered_map 선언할 때 <string, int> 로 해서 계속 오류났었다.  자나깨나 자료형 조심

 

문제 4. Valid Anagram

class Solution {
public:
    bool isAnagram(string s, string t) {
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return s == t;
    }
};

 

문제 5. Valid Palindrome

class Solution {
public:
    bool isPalindrome(string s) {
        
        string a, b;
        for (int i = 0; i<s.size(); i++) if (isalnum(s[i])) a += tolower(s[i]);
        b = a;
        reverse(b.begin(), b.end());
        return a == b;
    }
};

string 끼리 = 연산자를 사용한 복사는 깊은 복사다. alpha+numeric 인지 확인은 isalnum(), alpha인지 확인은 isalpha(), lower case로는 변경할 때는 tolower()을 사용한다. 숫자인지 확인은 isdigit()을 사용한다. 

 

 

문제 6. String to Integer (atoi)

atoi 부분만

class Solution {
public:
    int myAtoi(string res) {
        int sign = 1;
        int i = 0;
        if (res[0] == '-') {
            sign = -1;
            i ++;
        }
        
        int ans = 0;
        for (; res[i]!='\0';++i) ans = ans *10 + res[i] -'0';
        ans *= sign;
        
        if (ans >= INT_MAX) return INT_MAX;
        if (ans <= INT_MIN) return INT_MIN;
        return ans;
    }
};

전체 답

class Solution {
public:
  int myAtoi(string str) {
        if (str.empty()) return 0;
        int i = 0, sign = 1, n = str.size();
      
        while (i + 1 < str.size() && isspace(str[i])) ++i;      
        if (str[i] == '-') {
            sign *= -1; 
            i++;
        }
        else if (str[i] == '+') i++;
      
        long res = 0;
        while (i < n) {
            if (isdigit(str[i])) res = 10 * res + str[i++] - '0';
            else return res * sign;
            
            if (res > INT_MAX) return sign == -1 ? INT_MIN : INT_MAX;
        }
        return res * sign;
    }
};

어려웠다.

 

메모리는 많이 썼지만 런타임은 100.00%다.

 

문제 7.  Implement strStr()

class Solution {
public:
    int strStr(string haystack, string needle) {
        int m = haystack.size(), n = needle.size();
        for (int i = 0; i <= m - n; i++) {
            int j = 0;
            for (; j < n; j++) {
                if (haystack[i + j] != needle[j]) {
                    break;
                }
            }
            if (j == n) {
                return i;
            }
        }
        return -1;
    }
};

뒤로 갈수록 어려워지나보다.

 

문제 9. Longest Common Prefix

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string prefix="";
        if(strs.size()==0) return prefix;
        
        for(int j=0; j<strs[0].size(); j++){
            int i=1;
            for(; i<strs.size() && strs[i].size()>j; i++){
                if(strs[i][j]!=strs[0][j]) return prefix;
            }
            if(i==strs.size()) prefix+=strs[0][j];
        }
        return prefix;
    }
};