An ordered dictionary offers same time complexity as the standard dict. The implementation is simple: Keep two dictionaries and a doubly-linked list of keys. The DLL maintains order. One dict maps key => DLL node Other dict maps key => value Implementation details https://github.com/python/cpython/blob/3.7/Lib/collections/init.py#L129 Example Problem: Find the first non-repeating char in a string. def…
Tag: strings
Longest Palindrome Substring in a String
DP based solution class Solution(object): def __init__(self): self.lookup = {} def isPalindrome(self, s, dp, i, k): j = i + k – 1 if s[i] == s[j] and dp[i + 1][j – 1]: return True return False def longestPalindrome(self, s): “”” :type s: str :rtype: str “”” size = len(s) if size < 2: return…
Longest Substring without Repeating Characters
The solution uses a sliding window and uses O(n) time and O(n) space. There are many cases to take care of. We can skip the process string less than size 2. Iterate the string, checking each char as key in the hash, adding if not present. If not present in hash, add each char as…
Palindrome String Check With Non-alphanumeric Characters
class Solution(object): def isPalindrome(self, s): “”” :type s: str :rtype: bool “”” if len(s) < 1: return True start, end = 0, len(s) – 1 while start < end: # Loop till a special char is found while start < end and not s[start].isalnum(): start += 1 # Always keep the check start < end…
Check Two Strings are Anagrams?
class Solution(object): def isAnagram(self, s, t): “”” :type s: str :type t: str :rtype: bool “”” # Keep a frequency array frequency = {} for c in s: if c not in frequency: frequency[c] = 1 else: frequency[c] += 1 # Go over the other string for d in t: if d in frequency: frequency[d]…
Python Cheatsheet: Part II
Strings Since strings are immutable, each function creates a new string as output. – index(‘pat’) # return ValueError if pat not exist – find(‘pat’) # index or -1 x = “junkstringjunk” print(x.strip(“junk”)) # o/p = string String Slicing x = ‘mytestdata’ start = 0 end = 2 # One more than the needed index step…
How a Regex Engine Work?
A regular expression defines a set of string. A regex engine matches a pattern against input and returns true/false for the condition that pattern exists in the input. I have got a C++ implementation of a regex engine which uses simple constructs of matching the following: A single character An equal length pattern and input…
