Code Snippets¶

String Operations¶

Reverse Vowels¶

Given a string s, reverse only all the vowels in the string and return it. The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in both lower and upper cases, more than once.

def reverseVowels(s: str) -> str:
    L, R = 0, len(s) - 1
    vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'}
    token = list(s)
    while L <= R:
        if token[L] in vowels and token[R] in vowels:
            token[L], token[R] = token[R], token[L]
            L += 1
            R -= 1
        elif token[L] in vowels:
            R -= 1
        elif token[R] in vowels:
            L += 1
        else:
            L += 1
            R -= 1
    return ''.join(token)

Strobogrammatic Numbers¶

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

def isStrobogrammatic(num: str) -> bool:
    mapping = {
        '0': '0'
        , '1': '1'
        #, '2': '5' # one could consider 2 and 5 strobogrammatic
        #, '5': '2' # one could consider 2 and 5 strobogrammatic
        , '6': '9'
        , '8': '8'
        , '9': '6'
    }
    L, R = 0, len(num) - 1
    while L <= R:
        if num[L] not in mapping:
            return False
        expected = mapping[num[L]]
        if expected != num[R]:
            return False
        L += 1
        R -= 1
    return True

Time Complexity: \(\mathcal{O}(n)\)

Space Complexity: \(\mathcal{O}(1)\)

Reverse String¶

def reverseString(s: List[str]) -> None:
    """
    Do not return anything, modify s in-place instead.
    """
    L, R = 0, len(s) - 1
    while L <= R:
        s[L], s[R] = s[R], s[L]
        L += 1
        R -= 1

Time Complexity: \(\mathcal{O}(n)\)

Space Complexity: \(\mathcal{O}(1)\)

Rotate String¶

Given two strings s and goal, return true if and only if s can become goal after some number of shifts on s. A shift on s consists of moving the leftmost character of s to the rightmost position. For example, if s = "abcde", then it will be "bcdea" after one shift.

def rotateString(s: str, goal: str) -> bool:
    if len(s) != len(goal):
        return False
    return goal in f'{s}{s}'

Time Complexity: \(\mathcal{O}(n)\)

Space Complexity: \(\mathcal{O}(n)\)

Can be improved by improving the lookup method for instance using Knuth-Morris-Pratt (KMP) Algorithm.

Find the difference¶

You are given two strings s and t. String t is generated by random shuffling string s and then add one more letter at a random position. Return the letter that was added to t.

Bit ManipulationASCII Addition

XOR cancels out identical characters. Since t = s + 1 extra, after XOR-ing all characters from both strings, all identical characters become 0, and the extra one remains.

def findTheDifference(s: str, t: str) -> str:
    result = 0
    for c in s:
        result ^= ord(c)
    for c in t:
        result ^= ord(c)
    return chr(result)

Time Complexity: \(\mathcal{O}(n)\)

Space Complexity: \(\mathcal{O}(1)\)

Add the ASCII values of each character in each string. There will be a numeric delta, which can be converted to a ASCII character.
def findTheDifference(s: str, t: str) -> str:
    ans1 = sum([ord(c) for c in s])
    ans2 = sum([ord(c) for c in t])
    return chr(ans2 - ans1)

Time Complexity: \(\mathcal{O}(n)\)

Space Complexity: \(\mathcal{O}(1)\)

Ranges & Intervals¶

Missing Ranges¶

You are given an inclusive range [lower, upper] and a sorted unique integer array nums, where all elements are within the inclusive range. A number x is considered missing if x is in the range [lower, upper] and x is not in nums. Return the shortest sorted list of ranges that exactly covers all the missing numbers. That is, no element of nums is included in any of the ranges, and each missing number is covered by one of the ranges.

def findMissingRanges(nums: List[int], lower: int, upper: int) -> List[List[int]]:
    ans = []
    # iterate all the numbers in the array
    for num in nums:
        # when the current number larger than the current lower
        # that means there is a gap, add the gap into ans
        # the range is [lower, num - 1]
        if num > lower:
            ans.append([lower, num - 1])

        # otherwise, update the lower to the next integer after current number
        lower = num + 1

    # After go through all the number in the array
    # the lower will be the next integer of the last number
    # if there is a gap between the lower and the upper, append the range to the ans as result.
    if lower <= upper:
        ans.append([lower, upper])
    return ans

Meeting Attendance¶

Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings.

def canAttendMeetings(intervals: List[List[int]]) -> bool:
    if len(intervals) < 2:
        return True
    sorted_intervals = sorted(intervals, key=lambda ival: ival[1])
    for (_, e1), (s2, _) in zip(sorted_intervals, sorted_intervals[1:]):
        if e1 > s2:
            return False
    return True