대표적인 문자열 안에서 단어를 찾는 문자열 탐색 알고리즘

 

라빈-카프 알고리즘 : 

보이어-무어 알고리즘 : 

KMP 알고리즘 : 

아호-코라식 알고리즘 :

Suffix Array 맨버-마이어스 알고리즘 : 

LCP Array :

 

https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm

 

Rabin–Karp algorithm - Wikipedia

From Wikipedia, the free encyclopedia String searching algorithm In computer science, the Rabin–Karp algorithm or Karp–Rabin algorithm is a string-searching algorithm created by Richard M. Karp and Michael O. Rabin (1987) that uses hashing to find an

en.wikipedia.org

 

https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm

 

Boyer–Moore string-search algorithm - Wikipedia

From Wikipedia, the free encyclopedia String searching algorithm For the Boyer–Moore theorem prover, see Nqthm. In computer science, the Boyer–Moore string-search algorithm is an efficient string-searching algorithm that is the standard benchmark for p

en.wikipedia.org

https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

 

Knuth–Morris–Pratt algorithm - Wikipedia

From Wikipedia, the free encyclopedia Algorithm for finding sub-text location(s) inside a given sentence in Big O(n) time In computer science, the Knuth–Morris–Pratt algorithm (or KMP algorithm) is a string-searching algorithm that searches for occurre

en.wikipedia.org

https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm

 

Aho–Corasick algorithm - Wikipedia

From Wikipedia, the free encyclopedia String-searching algorithm Aho—Corasick AlgorithmA diagram of an Aho—Corasick automatonClassString Searching, String MatchingData structureFinite-state machine of strings In computer science, the Aho—Corasick a

en.wikipedia.org

https://en.wikipedia.org/wiki/Suffix_array

 

Suffix array - Wikipedia

From Wikipedia, the free encyclopedia Data structure for a string In computer science, a suffix array is a sorted array of all suffixes of a string. It is a data structure used in, among others, full-text indices, data-compression algorithms, and the field

en.wikipedia.org

https://en.wikipedia.org/wiki/LCP_array

 

LCP array - Wikipedia

From Wikipedia, the free encyclopedia In computer science, the longest common prefix array (LCP array) is an auxiliary data structure to the suffix array. It stores the lengths of the longest common prefixes (LCPs) between all pairs of consecutive suffixes

en.wikipedia.org

https://namu.wiki/w/%EB%AC%B8%EC%9E%90%EC%97%B4%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

문자열 알고리즘

말 그대로 문자열과 관련된 알고리즘 이다. 가장 대표적인 것이 문자열 검색(string search) 알고리즘이며

namu.wiki

 

저작자표시

'IT기술관련 > 알고리즘관련' 카테고리의 다른 글

정렬 알고리즘  (0) 2024.04.29
배열과 리스트 차이  (0) 2023.07.07
Baekjoon : Backtracking  (0) 2022.06.06
Baekjoon : Binary Search  (0) 2022.05.22
Baekjoon : Divide and Conquer  (0) 2022.05.22
제목 링크 난이도 풀이일 코드
[011] 274. H-Index LINK Medium 2024.04.21 class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int[] bucket = new int[n+1];
        for (int i = 0; i < n; i++) {
            int c = citations[i];
            if ( c>= n) {
                bucket[n]++;
            } else {
                bucket[c]++;
            }
        }
        int cnt = 0;
        for (int i = n; i >= 0; i--) {
            cnt += bucket[i];
            if (cnt >= i) {
                return i;
            }
        }
        return 0;
    }
}
[022] 380. Insert Delete GetRandom O(1) LINK Easy 2024.04.21 class RandomizedSet {

    Set<Integer> randomizedSet;
    

    public RandomizedSet() {
        if (randomizedSet == null) {
            randomizedSet = new HashSet();
        }
    }
    
    public boolean insert(int val) {
        if (randomizedSet.contains(val)) {
            return false;
        } else {
            randomizedSet.add(val);
            return true;
        }    
    }
    
    public boolean remove(int val) {
        if (randomizedSet.contains(val)) {
            randomizedSet.remove(val);
            return true;
        } else {
            return false;
        }   
    }
    
    public int getRandom() {
        Random random = new Random();
        int n = random.nextInt(randomizedSet.size());
        Object[] intArray = randomizedSet.toArray();
        return (int)intArray[n];
    }
}
[023] 238. Product of Array Except Self LINK Medium 2024.05.11 class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] left = new int[n];
        int[] right = new int[n];
        int[] answer = new int[n];
        left[0] = 1;
        for (int i = 1; i < n; i++) {
            left[i] = left[i-1] * nums[i-1];
        }
        right[n-1] = 1;
        for (int j = n-2; j >= 0; j--) {
            right[j] = right[j+1] * nums[j+1];
        }
        for (int i = 0; i < n; i++) {
            answer[i] = left[i] * right[i];
        }
        return answer; 
    }
}
         
         
         
         
         
저작자표시

'코딩테스트 > Leetcode' 카테고리의 다른 글

Leetcode 문제풀이 001 - 010  (0) 2024.04.14
Leetcode 용어  (0) 2024.04.14
제목 링크 난이도 풀이일 코드
[001] 88. Merge Sorted Array LINK Easy 2024.03.09 class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = m, j = 0; i < m+n; i++, j++) {
            nums1[i] = nums2[j];
        }
        Arrays.sort(nums1);
    }
}
[002] 27. Remove Element LINK E 2024.03.09 class Solution {
    public int removeElement(int[] nums, int val) {
        int head = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[head++] = nums[i];
            }
        }
        return head;
    }
}
[003] 26. Remove Duplicates from Sorted Array LINK   2024.04.14 class Solution {
    public int removeDuplicates(int[] nums) {
        int j = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i-1] != nums[i]) {
                nums[j++] = nums[i];
            }
        }
        return j;    
    }
}
[004] 80. Remove Duplicates from Sorted Array II LINK M 2024.04.14 class Solution {
    public int removeDuplicates(int[] nums) {
        int j = 1;
        for (int i = 1; i < nums.length; i++) {
            if (j == 1 || nums[j-2] != nums[i]) {
                nums[j++] = nums[i];
            }
        }
        return j;
    }
}
[005] 169. Majority Element LINK E 2024.04.15 class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length /2];
    }
}
[006] 189. Rotate Array LINK M 2024.04.15 class Solution {
    public void rotate(int[] nums, int k) {
        int[] result = new int[nums.length];
        if (nums.length < k) {
            k = k % nums.length;
        }
        for (int i = 0; i < nums.length; i++) {
            if (i+k < nums.length) {
                result[i+k] = nums[i];
            } else {
                result[i+k-nums.length] = nums[i];
            }
        }
        for (int i = 0; i < result.length; i++) {
            nums[i] = result[i];
        }
    }
}
[007] 121. Best Time to Buy and Sell Stock LINK E 2024.04.15 class Solution {
    public int maxProfit(int[] prices) {
        int buy = prices[0];
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (buy > prices[i]) {
                buy = prices[i];
            } else if (prices[i] - buy > profit) {
                profit = prices[i] - buy;
            }   
        }
        return profit;
    }
}

NO : O(N^2) : stupid
class Solution {
    public int maxProfit(int[] prices) {
        int maxprofit = 0;
        for (int i = 0 ; i < prices.length; i++) {
            if (prices[i] < prices[j]) {
                for (int j = i+1; j < prices.length; j++) {
                    if (prices[i] < prices[j]) {
                        int current_profit = prices[j] - prices[i];
                        if (maxprofit < current_profit) {
                            maxprofit = current_profit;
                        }
                    }     
                }
            }
        }
        if (maxprofit > 0) {
            return maxprofit;
        } else {
            return 0;
        }
    }
}
[008] 122. Best Time to Buy and Sell Stock II LINK M 2024.04.16 class Solution {
    public int maxProfit(int[] prices) {
        boolean hasStock = false;
        int buy = 0;
        int profit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (i+1 < prices.length && prices[i] < prices[i+1] && hasStock == false) {
                // buy
                buy = prices[i];
                hasStock = true;
            }
            if (i+1 < prices.length && prices[i] > prices[i+1] && hasStock == true) {
                // sell;
                profit += (prices[i] - buy);
                hasStock = false;
            }
            if (i+1 == prices.length && hasStock == true) {
                // sell;
                profit += (prices[i] - buy);
                hasStock = false;
            }
        }
        return profit;        
    }
}

// better
class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        for(int i=1;i<prices.length;i++) {
            if(prices[i] > prices[i-1]) {
                profit += prices[i] - prices[i-1];
            }
        }
        return profit;
    }
}
[009] 55. Jump Game LINK M 2024.04.16 // wrong
class Solution {
    public static boolean canJump(int[] nums) {
        int reach = nums[0];
        for (int i = 0; i < nums.length;i++) {
            if (reach == nums.length-1) {
                return true;
            } else if (reach > nums.length-1) {
                return false;
            }
            reach = reach + nums[i];
            System.out.println(String.format("nums[i]=%s", i));
        }
        return false;
    }
}

// better
class Solution {
    public boolean canJump(int[] nums) {
        int reach = 0;
        for (int i = 0 ; i < nums.length; i++) {
            if (i > reach) {
                return false;
            }
            reach = Math.max(reach, i+nums[i]);
        }
        return true;
    }
}
[010] 45. Jump Game II LINK M 2024.04.16 class Solution {
    public int jump(int[] nums) {
        int jumps = 0, curEnd = 0, curFarthest = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            curFarthest = Math.max(curFarthest, i + nums[i]);
            if (i == curEnd) {
                jumps++;
                curEnd = curFarthest;
            }
        }
        return jumps;
    }
}

https://bcp0109.tistory.com/280
저작자표시

'코딩테스트 > Leetcode' 카테고리의 다른 글

Leetcode 문제풀이 011 - 020  (0) 2024.04.21
Leetcode 용어  (0) 2024.04.14

+ Recent posts

티스토리툴바