16주(Longest Substring)

16주(Longest Substring)

디렉토리:

이번 주 문제 완성

주요 과정 사고방식

관련 코드

1. 이번 주에 문제 완성

이번 주에는 총 2문항, 2문항을 완성했다.주로 하위 문자열에 관한 두 가지 문제입니다.
구체적인 완성 문제 및 난이도는 다음과 같다.
#
Title
Difficulty
3
Longest Substring Without Repeating Characters
Medium
5
Longest Palindromic Substring
Medium

제목 내용

1、Longest Substring Without Repeating Characters　 Given a string, find the length of the longest substring without repeating characters.
Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

제목의 뜻: 알파벳이 중복되지 않은 가장 긴 하위 문자열의 길이를 되돌려줍니다.(주: 하위 서열이 아니라 하위 문자열이 연속적임을 주의하십시오)
2、Longest Palindromic Substring　 Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

제목 대의: 문자열을 주고 가장 긴 문자열을 되돌려줍니다.

2. 주요 과정 사고방식

1、Longest Substring Without Repeating Characters：

이 문제의 해결 핵심은 출현한 문자가 나타날 때 현재 하위 문자의 시작 위치를 뒤로 옮겨 중복을 방지하는 것이다.보조적인 그룹 (모두 -1로 초기화) 을 이용하여 모든 숫자가 가장 최근에 나타난 위치를 기록할 수 있다.만약 최근에 나타난 위치가 start보다 크다면 (start는 현재 하위 문자열의 초기 위치 - 1, 초기화 - 1) start의 위치를 이전 같은 문자가 나타난 위치로 뒤로 이동해야 합니다.리셋과 현재 하위 문자열의 길이를 판단하고 비교적 긴 것을 선택하여 저장합니다.마지막으로 보조 그룹 중의visit[s[i]=i를 업데이트합니다.

    ，      “babc”。

우선visit[b]=-1에 접근합니다.그래서result=max(0,0-(-1)=1이 있습니다.visit[b]=0; 두 번째 b를 방문했을 때visit[b]=0>start로 인해 start가 0으로 바뀌었습니다.즉, a의 위치에서 새로운 하위 문자열로 반복되는 것을 피합니다.visit[b]가 2로 업데이트되어 최신 b의 출현 위치가 2임을 나타낸다.이렇게 계속 방문하면 마지막으로result=3을 얻을 수 있습니다.

2、Longest Palindromic Substring：

이 문제는 하위 문자열을 풀기 위한 문제입니다.여기서 주로 사용하는 방법은 매번 i를 하위 문자열의 중간 위치로 하고 같은 문자를 건너뛴 후에 k와 j를 각각 서열의 끝과 시작에 방문하도록 설정하고 양쪽이 같으면 계속 방문하고 반대로 멈추는 것이다.s[i]를 중간항으로 하는 회문 서브 문자열의 길이는 k-j+1입니다.새 길이가 더 길면 새 시작 위치 j와 길이를 기록합니다.마지막으로 s의 하위 문자열 s.substr(start,len max)에 접근하면 마지막 결과를 얻을 수 있습니다.

3. 관련 코드

Longest Substring Without Repeating Characters

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> visit(256, -1);
        int start=-1,result=0;
        for(int i=0;iif(visit[s[i]]>start){
                start=visit[s[i]];
            }
            result=max(result,i-start);
            visit[s[i]]=i; 

        }
        return result;
    }
};

Longest Palindromic Substring

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.empty()) return "";
        if(s.size()==1) return s;
        int len_max = 1; int start=0;
        for(int i=0; isize()-1;){
            if(s.size()-i<=len_max/2) break;
            int j=i, k=i;
            while(ksize()-1&&s[k+1]==s[k]) k++;   //      
            i = k+1;
            while(k < s.size()-1 && j > 0 && s[k+1] == s[j-1]) {
                k++;
                j--;
            }
            int temp = k-j+1;
            if (temp > len_max) { 
                start = j; len_max = temp; 
            }
        }
        return s.substr(start, len_max);
    }
};