strings – Simplify Complexities

Why Use Python Ordered Dictionary?

March 8, 2020

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 … More Why Use Python Ordered Dictionary?

Longest Palindrome Substring in a String

January 27, 2020

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 … More Longest Palindrome Substring in a String

Longest Substring without Repeating Characters

January 25, 2020

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 … More Longest Substring without Repeating Characters

Palindrome String Check With Non-alphanumeric Characters

January 19, 2020

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 … More Palindrome String Check With Non-alphanumeric Characters

Check Two Strings are Anagrams?

January 16, 2020

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] … More Check Two Strings are Anagrams?

Python Cheatsheet: Part II

December 22, 2019

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 … More Python Cheatsheet: Part II

How a Regex Engine Work?

September 22, 2019

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 … More How a Regex Engine Work?

Simplify Complexities

O(1)

Tag: strings