leetcode
LeetCode ๐๏ธ/String
647. Palindromic Substrings
Description: Solution: In for loop, we have two parts: odd number length & even number length. In odd number case, we expand our l & r pointers to both sides, and get the number of palindromic. In even number case, we do same thing, but l & r pointer starts with different location. (i, i+1)
LeetCode ๐๏ธ/String
125. Valid Palindrome
Description: Solution: Let's make left pointer & right pointer. isalnum() makes sure the char is whether char or not. If one of those is not char, then we move the pointer. Space Complexity: O(1)
LeetCode ๐๏ธ/String
20. Valid Parentheses
Description: Solution: In pariHash, we set close parentheses as a key, and open parentheses as a value. If the c is open parentheses, we append on stack. If the c is closing parentheses, we search the last value of stack "stack[-1]" and compare it with its key. We can pop the stack. If the stack is empty at the end of the solution, we can return True. Time Complexity: O(n) Space Complexity: O(n)
LeetCode ๐๏ธ/String
49. Group Anagrams
Description: Solution: We use hashtable for this problem. In hashtable, the key is the sorted value(ex. aet, ant, abt in example 1) if keyString is not the key in table, we make the new list for it. Then, we append s to the appropriate key. Time Complexity: O(m*nlogn) Space Complexity: O(n)
LeetCode ๐๏ธ/String
242. Valid Anagram
Description: Solution: We use soft() to rearrange the character. See "s == t".
LeetCode ๐๏ธ/String
424. Longest Repeating Character Replacement
Description: Solution: count will store the number of letters of each chracters. res is the longest length of substring we can have. There will be two pointers: r, l Moving r pointer, we count the character. If the length(substring) - (count of bigger character) is bigger than k, we should move l pointer. Then, update the max res. Time Complexity: O(n)
LeetCode ๐๏ธ/String
3. Longest Substring Without Repeating Characters
Description: Solution: We use set() for substring. (Sliding Window) In example 1, the string is abcabcbb. We are gonna store substring until meet duplicated character. abc -> now we meet "a" Remove the first "a", now new substring is bca. The length of substring should be r - l + 1. Time Complexity: O(n) Space Complexity: O(n)
LeetCode ๐๏ธ/Tree
211. Design Add and Search Words Data Structure
Description: Solution: For solving this problem, we use TrieNode (prefix tree). In serach(), we use recursion method to check "." if c is "." we are gonna check the values next to the "." We put the values in dfs() from the next one, so that check recursively by increasing i.
