Why Use Python Ordered Dictionary?

Leave a comment

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 firstUniqChar(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s) == 0:
            return -1

        d = collections.OrderedDict()
        
        for index, c in enumerate(s):
            if c in d:
                d[c][0] += 1
            else:
                d[c] = [1, index]
        
        for k in d:
            if d[k][0] == 1:
                return d[k][1]
        
        return -1

Longest Palindrome Substring in a String

Leave a comment

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 s
        
        dp = [ [False]*size for c in range(size+1) ]
        
        i = j = 0
        longest = 0
        startIndex = endIndex = 0
        
        while i < size:
            dp[i][i] = True
            
            # Handle the case of two repeated chars ('bb')
            j = i + 1
            if j < size:
                if s[i] == s[j]:
                    dp[i][j] = True
                    
                    # Always update the index for result.
                    startIndex = i
                    endIndex = j
                    longest = 2
            i += 1
        
        # Start finding substrings longer the 2.            
        k = 3
        while k <= size:
            for i in range(0, size - k + 1):
                if self.isPalindrome(s, dp, i, k):
                    dp[i][i+k-1] = True
                    strLen = k
                    
                    if strLen > longest:
                        longest = strLen
                        startIndex = i
                        endIndex = i + k - 1
            k += 1
            
        return s[startIndex: endIndex + 1]

Resources

Written with StackEdit.

Longest Substring without Repeating Characters

Leave a comment

The solution uses a sliding window and uses O(n) time and O(n) space.
There are many cases to take care of.

  1. We can skip the process string less than size 2.
  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 key and index as value.
  3. If present in hash, check if the index is more than the window start.
    Calculate the window size and update max.
  4. Check the max again at the time of return.
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s) < 2:
            return len(s)
        
        wstart = wend = 0
        charMap = {}
        maxLen = 0
        currentLen = 0
        
        while wend < len(s):
            if s[wend] in charMap and charMap[s[wend]] >= wstart: #abba
                currentLen = wend - wstart
                maxLen = max(maxLen, currentLen)
                wstart = charMap[s[wend]] + 1
            
            charMap[s[wend]] = wend
            wend += 1
        
        # The expression wend - wstart gets the case of last
        # character used for len count.
        return max(maxLen, wend - wstart)

Reference

Written with StackEdit.

Palindrome String Check With Non-alphanumeric Characters

Leave a comment 
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
            while start < end and not s[end].isalnum():
                end -= 1
            
            # For a pure non-alnum string e.g. "..", start = end = 1
            # The next iteration will have start +=1 => 2
            # So breaking the loop correctly.
            
            if s[start].lower() != s[end].lower():
                return False
            
            start += 1
            end -= 1
            
        return True

Reference

Written with StackEdit.

Check Two Strings are Anagrams?

Leave a comment 
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] -= 1
                if frequency[d] == 0:
                    # Just keep deleting what is not required
                    del frequency[d]
            else:
                # Anything not in dict, just say Not an Anagram.
                return False

        if len(frequency) == 0:
            return True
        
        return False

Written with StackEdit.

Python Cheatsheet: Part II

Leave a comment

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 = 1
print(x[start:end:step]) # my

x = 'mytestdata'
print(x[::-1]) # Iterates the string from last (start = 0 + step = (-1))

s = 'astring'
print(s[-1:]) # prints g

# Start from the last and move iterator by negative 1
s = 'astring'
print(s[-1:0:-1]) # reverses the string

Written with StackEdit.

How a Regex Engine Work?

Leave a comment

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:

  1. A single character
  2. An equal length pattern and input
  3. A pattern that has ^ and $
  4. Wildcards (? and *)

It is inspired by https://nickdrane.com/build-your-own-regex/ and https://swtch.com/~rsc/regexp/regexp1.html.

The code is as following:

#include<iostream>

using namespace std;

bool MatchQuestion(const char * pattern, const char *input);
bool MatchStar(const char *pattern, const char *input);

bool matchOne(char pattern, char input)
{
  cout << "matchOne" << "patt=" << pattern << "input=" << input << endl;
 if (pattern == '\0')
     return true;

  if (input == '\0')
      return false;

  return pattern == input;
}

bool MatchSameLength(const char *pattern, const char* input) 
{
    if (*pattern == '\0')
        return true;

    return matchOne(pattern[0], input[0]) && MatchSameLength(pattern+1, input+1);
}

bool MatchAnywhere(const char *pattern, const char *input)
{
    //cout << "patt=" << *pattern << "input=" << *input << endl;
    if (*pattern == '\0')
        return true;

    if (*pattern == '$' && *input == '\0')
        return true;

    if (pattern[1] == '?') {
        return MatchQuestion(pattern, input);
    }

    if (pattern[1] == '*') {
        return MatchStar(pattern, input);
    }

    return matchOne(pattern[0], input[0]) && MatchAnywhere(pattern+1, input+1);
}

bool MatchQuestion(const char * pattern, const char *input)
{
    return (
        MatchAnywhere(pattern+2, input) ||
            (matchOne(*pattern, *input) && MatchAnywhere(pattern+2, input))
            );
}

bool MatchStar(const char *pattern, const char *input)
{
 return (
     MatchAnywhere(pattern+2, input) ||
     (matchOne(*pattern, *input) && MatchAnywhere(pattern, input+1))
 );
}

bool search(const char *pattern, const char *input )
{
    if (*pattern == '^') {
        return MatchAnywhere(pattern+1, input);
    }

    while (*input) {
        if (MatchAnywhere(pattern, input))
            return true;
        ++input;
        }
    return false;    
}

int main() {
    //cout << MatchSameLength("aab", "aab") << endl;
    //cout << MatchAnywhere("^b$", "b") << endl;

    cout << search("ax*b", "abc") << endl;
    return 1;
}
References

Written with StackEdit.