leetCode - daily coding

오늘의 leetCode 알고리즘 풀어본 문제를 봐보자

 

5. Longest Palindromic Substring

먼저 가장 긴 펠린드롬 문제

 

문제 요약 - 주어진 스트링에서 

뒤집어도 똑같은 문자 - 펠린드롬 문자 중 가장 긴 문자를 찾아서 return 시키는 문제다

 

문제 풀이 - 이 문제는 다이나믹 프로그래밍으로 풀었다.

생각을 어떻게 해야하냐면 , 

일단 펠린드롬을 찾기위해서는 2중 for문을 돌아야하는데,

첫번째 기준 문자와 두번째 기준 문자가 같을때  , 

안에 있는 문자가 1개 밖에 없거나 , 이 문자 전까지 즉 [i-1][j+1] 까지가 동일한 문자였으면 

팰린드롬이라고 할 수 있다.

그 찾은 문자중에 가장 긴 문자를 return 하면 된다.

 

문제 정답 - 

https://github.com/kwonhyucknae/algorithm_study/commit/01c7ba45a1190f2ebfae99c0a103d17822d14e5f

 

 

Longest Substring Without Repeating Characters

 

 

문제 요약 - 문자열 중에서 반복되는 char 이 없는 것 중에 

가장 긴 문자열의 길이를 찾는 문제

 

문제 풀이 - 슬라이딩 윈도우 를 배움..

2개의 i , j 의 int 값을 두고

HashSet 에 문자열을 1개씩 add 하고 set 에 없으면 i++ , 있으면 j ++ 

이렇게 창문 처럼 한칸씩 옮겨간다.

 

문제 정답 - 

https://github.com/kwonhyucknae/algorithm_study/commit/befc63449fa3ab5906ed2d0504cfe1fc5b0e2fe9