스트링 관련 leetcode 문제 - #include <blog.cxx.kr>

ide 를 사용하지 않고 문제를 풀어보기로
leetcode 의 경우 include 에 대해 명시하지 않아도 사전에 include 되어 있는 라이브러리들이 대다수

https://leetcode.com/problems/valid-palindrome/
125. Valid Palindrome

class Solution {
public:
    bool isalnu(const char& c){
        if(c >='a' && c<='z'){
            return true;
        } else if(c >='A' && c<='Z'){
            return true;
        } else if(c >='0' && c<='9'){
            return true;
        }  
        return false;
    }
    bool lowerCMP(const char& c, const char& c2){
        if(c >='A' && c <='Z' && c2 >='a' && c2 <='z'){
            return c+32 == c2;
        } else if(c2 >='A' && c2 <='Z' && c >='a' && c <='z'){
            return c == c2+32;
        }
        return c == c2;
    }
    bool isPalindrome(string s) {
        size_t ri = s.length()-1;
        size_t i = 0;
        
        while(i < ri){            
            char& left = s[i];
            char& right = s[ri];
            
            if(isalnu(left) == false){
                i++;
                continue;
            }
            if(isalnu(right) == false){
                ri--;
                continue;
            }
            if(lowerCMP(left,right)){
                ++i;
                --ri;
                continue;
            } else{
                return false;
            }
        }
        
        return true;
    }
};

https://leetcode.com/problems/reverse-string/
344. Reverse String

class Solution {
public:
    void reverseString(vector<char>& s) {
        if(s.size()==0){
            return;
        }
        size_t i = 0;
        size_t ri = s.size()-1;
        
        while(i < ri){
            auto temp = std::move(s[i]);
            s[i] = std::move(s[ri]);
            s[ri] = std::move(temp);
            ++i;
          	--ri;
        }
    }
};

https://leetcode.com/problems/reorder-data-in-log-files/
937. Reorder Data in Log Files

https://leetcode.com/problems/most-common-word/
819. Most Common Word
테스트케이스 단어의 구분자가 ‘ ‘ 공백 ‘,’ 콤마로 복합적인데 그걸 간과하고 stringstram getlin 으로 tokenize 하려고 하다가 코드가 꼬였다 실제는 단어보다 char 단위로 완전 탐색하며 단어를 구분짓고 hashtable 처리해야 할듯
추가로 map 에 대한 for access 시 신규 기능인 structured binding 을 사용하면 좀더 깔끔할듯
완전 탐색으로 alphanumeric 이 아닌 경우를 단어구분 조건으로 잡았으나 단일 단어 입력 시 해당조건을 사용할 수 없으며 alphanumeric 이 아닌 경우의 케이스에 무조건 hashtable 에 해당 cur string 이 연산되는 현ㅅ상을 예외처리함 좋지않다..

#include <unordered_map>

class Solution {
public:
    bool isalnu(const char& c){
        if(c >='a' && c<='z'){
            return true;
        } else if(c >='A' && c<='Z'){
            return true;
        } else if(c >='0' && c<='9'){
            return true;
        }  
        return false;
    }
    string mostCommonWord(string paragraph, vector<string>& banned) {
        unordered_map<string,int> wordCnt;
        
        paragraph+=" ";
        string cur;
        for(auto& c : paragraph){
            if(isalnu(c)){
                cur += tolower(c);
            } else if(cur!="") {
                wordCnt[cur]++;
                cur="";
            }
        }
        
        for(auto x : banned){
            wordCnt[x] = 0;
        }
        
        int mostC = 0;
        string retMost = "";
        for(auto [first, second] : wordCnt){
            if(mostC < second){
                retMost = first;
                mostC = second;
            }
        }
            
        return retMost;
    }
};

https://leetcode.com/problems/group-anagrams/
49. Group Anagrams
(sort 이외에 alpha count 를 이용한 hash 값을 직접 구하면 좀더 빠르다)

#include <unordered_map>

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ret;
        unordered_map<string,vector<string>> hTable;
        for(auto&& cur : strs){
            auto sCur = cur;
            sort(sCur.begin(), sCur.end());
            
            hTable[sCur].push_back(move(cur));
        }
        
        for(auto&& cur : hTable){
            ret.emplace_back(move(cur.second));
        }
        return ret;
    }
};

https://leetcode.com/problems/longest-palindromic-substring/
5. Longest Palindromic Substring

https://leetcode.com/problems/valid-anagram/submissions/
242. Valid Anagram

class Solution {
public:
    bool isAnagram(string s, string t) {
        array<int,'z'-'a'+1> alphas={0,};
        
        for(auto&& c : s){
            ++alphas[c-'a'];
        }
        
        for(auto&& c : t){
            --alphas[c-'a'];
        }        
        
        for(auto&& c : alphas){
            if(c!=0)
                return false;
        }
        return true;
    }
};

https://leetcode.com/problems/rotate-string/
796. Rotate String

변칙적인 방법.. 한 단어의 순환은 결국 A+A 로 표현가능

class Solution {
public:
    bool rotateString(string A, string B) {
        if(A.length() == B.length()){
            A = A+A;
            if(A.find(B) != std::string::npos){
                return true;
            }
        }
        return false;
    }
};

댓글 남기기 댓글 취소