String Algorithms

decodeString.py

def decodeString(self, s):
    """
    s = "3[a]2[bc]", return "aaabcbc".
    s = "3[a2[c]]", return "accaccacc".
    s = "2[abc]3[cd]ef", return "abcabccdcdcdef".
    """

    stack = []; coeff = 0; ans = ''

    for c in s:
        if c == '[':
            stack.append(ans)
            stack.append(coeff)
            ans = ''
            coeff = 0
        elif c == ']':
            num = stack.pop()
            prevString = stack.pop()
            ans = prevString + num*ans
        elif c.isdigit():
            coeff = coeff*10 + int(c)
        else:
            ans += c
        print(stack, ans, coeff)
    return ans

is_pangram.py

# A pangram is a sentence using every letter of a given alphabet at least once.
is_pangram = lambda s: not set('abcdefghijklmnopqrstuvwxyz') - set(s.lower())

lengthOfLongestSubstring.java

/*
Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3.
*/
public int lengthOfLongestSubstring(String s) {
        
        Map<Character, Integer> map= new HashMap<>();
        int start=0, len=0;
        
        // abba
        for(int i=0; i<s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                if (map.get(c) >= start) 
                    start = map.get(c) + 1;
            }
            len = Math.max(len, i-start+1);
            map.put(c, i);
        }
        
        return len;
    }

longest_common_prefix.py

"""
Input: ["flower","flow","flight"]
Output: "fl"
"""


def longest_common_prefix(words) -> "str":
    if not words:
        return ""

    shortest_word = min(words, key=len)

    for i, letter in enumerate(shortest_word):
        for s in words:
            if s[i] != letter:
                return shortest_word[:i]

    return shortest_word

reverse_string.py

def reverse_string(s): 
    if len(s) == 1:
        return s
    return s[-1] + rev(s[:-1])

string_compression.py

def string_compression(string):
    counter = 0
    compressed = ""
    previous_letter = string[0]

    for letter in string:
        if letter != previous_letter:
            compressed = compressed + previous_letter + str(counter)
            counter = 0
        counter += 1
        previous_letter = letter

    compressed = compressed + previous_letter + str(counter)

    return compressed


def test_string_comp():
    return string_compression("aaaabbcccccaaabb") == "a4b2c5a3b2"