Longest Substring Without Repeating Characters

yyeahh·2020년 10월 3일
0

LeetCode

목록 보기
4/9

Lognest Substring Without Repeating Characters

|| 문제설명 ||

  1. string s가 주어질때, 반복된 문자가 없는 가장 긴 부분문자열(substring)을 구하시오.

    Input: s = "abcabcbb"
     Output: 3
     Explanation: The answer is "abc", with the length of 3.
  • Input

    string s
  • Output

    int

|| 문제해결과정 ||

int answer

- 중복되는 문자를 없애는 것이 아닌 중복없는 부분중 가장 긴 부분을 추출하는 것이다.
- 영문자, 숫자, 기호, 공백이 포함된 s (아스키코드로 32 ~ 126번 안에 존재), chk
1) 함수 호출 방식
- 새로운 함수 cnt를 구현
: cnt(string s, int& from, vector<int> chk);
- 사용한 문자는 chk[s[i]] = i + 1을 통해 제외시키고, 나중에 제외시킨 문자가 등장했을때 함수를 종료시키면서 증가시킨 ans만큼 return;
- 이때, from에 chk[s[i]]를 저장해서 다음에 시작할 장소를 저장해둠.
- cnt함수가 끝날 때마다 return된 값을 answer와 비교하여 큰값을 저장 

|| 코드 ||

[2020.10.03] 성공
class Solution {
public:
    bool exit = false;
    int lengthOfLongestSubstring(string s) {
        int answer = 0, from = 0;
        vector<int> chk(128, 0);
        
        while(!exit) {
            int count = cnt(s, from, chk);
            if(answer < count) answer = count;
        }
        return answer;
    }
    int cnt(const string s, int& from, vector<int> chk) {
        int ans = 0;
        for(int i = from; i < s.size(); i++) {
            if(!chk[s[i]]) {
                chk[s[i]] = i + 1;  // 해당 문자가 있는 (위치 + 1) 저장
                ans++;
            }
            else {  // 종료
                from = chk[s[i]];                
                return ans;
            }
        }
        // 문자열의 마지막까지 돌았을 때
        exit = true;
        return ans;
    }
};


결론 = 매우 좋지 못한 코드이다...


[2020.10.03] 실패
  • 함수 호출 대신 하나의 while()/for()으로 끝낼 방법 모색
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int answer = 0, start = 0;
        bool c = false;
        vector<int> chk(128, 0);
        
        for(int i = 0; i < s.size();) {
            if(start > chk[s[i]] - 1) {
                chk[s[i]] = i + 1;  // 해당 문자가 있는 (위치 + 1) 저장
                i++;
            }
            else {
                if(answer < i - start) answer = i - start;
                start = i = chk[s[i]];
                c = true;
            }          
        }
        return answer;
    }
};

Input : " " | Output : 0 | Expected : 1

else 를 거치지 않는 그대로가 답이 경우에 대한 예외가 빠짐
if(!c) answer = s.size();

0개의 댓글