넘치게 채우기

https://leetcode.com/problems/find-the-length-of-the-longest-common-prefix/description/?envType=daily-question&envId=2024-09-24leetcode - Find the Length of the Longest Common Prefix문제 유형 : 트라이(Trie), 문자열 처리, 해시문제 난이도 : Medium 문제You are given two arrays with positive integers arr1 and arr2.A prefix of a positive integer is an integer formed by one or more of its digits, starting from its leftmos..

https://leetcode.com/problems/shortest-palindrome/description/?envType=daily-question&envId=2024-09-20leetcode - Shortest Palindrome문제 유형 : 팰린드롬, 문자열 처리, KMP 알고리즘문제 난이도 : Hard 문제You are given a string s. You can convert s to a palindrome by adding characters in front of it.Return the shortest palindrome you can find by performing this transformation. 문자열 s를 받는다. 당신은 s에 접두사를 붙여서 변환시킬 수 있다.s에 문자를 ..

설명Knuth, Morris, Pertt이 만든 문자열 패턴 검색 알고리즘인 KMP 알고리즘은O(n+m)에 문자열 패턴을 검색해낼 수 있다. 이 알고리즘의 핵심은 lps 배열이다.lps = Longest Prefix Suffix.각 위치까지의 부분 문자열에서 자기 자신의 접두사이면서 접미사인 가장 긴 길이를 저장한 배열이다.패턴 내에서 일치하지 않는 문자가 발견되면, 이전에 계산한 lps를 이용하여 패턴을 적절히 이동한다.lps[i]는 0부터 i-1까지는   LPS 배열의 생성방법은 다음과 같다:lps[0]와 len을 0으로 초기화한다. len은 가장 긴 접두사와 접미사 값의 길이이다.pat[len]과 pat[i]가 일치하면, len을 1 증가하고, 증가된 값을 lps[i]에 할당한다.일치하지 않고 le..

설명Naive 패턴 검색에서는, 우리는 모든 pattern의 길이와 같은 부분문자열들을 원본 문자열에서 추출해서 각각 한 글자씩 비교했다. Rabin-Karp 알고리즘에서도, 모든 부분문자열을 검사하지만, 대신 패턴의 해시 값와 현재 부분문자열의 해시 값을 비교한다.그리고 해시 값이 매칭되면, 패턴이 맞는 것이다.Rabin-Karp 알고리즘은 다음의 해시 값들을 계산할 필요가 있다:패턴의 해시 값더미 문자열(haystack)에서의 길이가 m인 모든 부분문자열해시 값은 문자열에서 패턴을 찾는 데 효율적으로 사용된다.해시 값은 rolling hash function으로 계산되는데, 기존의 글자를 하나 버리고 새 글자를 가져오면서 해시 값을 업데이트하면 된다.롤링 해시 함수의 과정은 다음과 같다:기저 수 b와..

설명Naive 패턴 검색 알고리즘은, 문자열에서 패턴을 찾는 가장 단순한 방법이다.패턴을 텍스트 위로 하나씩 밀어서 일치하는지 확인하고, 일치하는 것이 발견되면, 1개씩 다시 밀어서 다음에 일치하는 항목을 확인한다. 코드(C++)#include #include using namespace std;void search(string &pat, string &txt) { int M = pat.size(); int N = txt.size(); for (int i = 0; i   Example 1: pattern found at: 0pattern found at: 9pattern found at: 12Example 2: pattern found at: 1  복잡도 분석시간 복잡도: O(n * m)..

https://leetcode.com/problems/different-ways-to-add-parentheses/description/?envType=daily-question&envId=2024-09-19leetcode - Different Ways to Add Parentheses문제 유형 : 문자열 처리, 재귀, 다이나믹 프로그래밍, 카탈란 수문제 난이도 : Medium 문제Given a string expression of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. You may return the answe..

https://leetcode.com/problems/largest-number/description/?envType=daily-question&envId=2024-09-18leetcode - Largest Number문제 유형 : 문자열 처리, 정렬문제 난이도 : Medium 문제Given a list of non-negative integers nums, arrange them such that they form the largest number and return it.Since the result may be very large, so you need to return a string instead of an integer. 음이 아닌 정수 nums를 받는다. 이 수들을 나열하여 만들 수 있는 가..

https://leetcode.com/problems/uncommon-words-from-two-sentences/description/?envType=daily-question&envId=2024-09-17leetcode - Uncommon Words from Two Sentences문제 유형 : 문자열 처리, 해시문제 난이도 : Easy 문제A sentence is a string of single-space separated words where each word consists only of lowercase letters.A word is uncommon if it appears exactly once in one of the sentences, and does not appear in the ..

https://leetcode.com/problems/minimum-time-difference/description/?envType=daily-question&envId=2024-09-16leetcode - Minimum Time DIfference문제 유형 : 정렬, 문자열 처리문제 난이도 : Medium 문제Given a list of 24-hour clock time points in "HH:MM" format, return the minimum minutes difference between any two time-points in the list. "HH:MM"의 형식으로 24시간기준의 시간이 배열로 주어진다.두 시간의 최소 시간차를 분단위의 정수로 구하시오. 풀이우선, 모든 시간을 분단위로 ..

https://leetcode.com/problems/count-the-number-of-consistent-strings/description/?envType=daily-question&envId=2024-09-12leetcode - Count the Number of Consistent Strings문제 유형 : 문자열 처리문제 난이도 : Easy 문제You are given a string allowed consisting of distinct characters and an array of strings words. A string is consistent if all characters in the string appear in the string allowed.Return the number ..