# Leetcode - Episode 11 - Faster than 99.17% (1 x M, 2 x E)

Watch out string problems: I'm coming for you.

I really feel like I'm graduating from String School and feel fairly comfortable with a few different techniques for solving string-based puzzles. I get my fastest run times in this area as well.

Not too much else to report. I've also been reading up on permutation algorithms and reviewing the trade-offs between BFS and DFS.

### Reverse Vowels of a String

Problem: Reverse the vowels of a given string.

I instantly knew that I wanted to go for a two pointer solution for this. I'm not sure if there's a more efficient way, in fact.

`class Solution(object):    def reverseVowels(self, s):        """        :type s: str        :rtype: str        """        s = list(s)        vowels = set('aeiouAEIOU')                start = 0        end = len(s)-1        while not start >= end:            if s[start] not in vowels:                start += 1                continue            if s[end] not in vowels:                end -= 1                continue            s[start], s[end] = s[end], s[start]            start += 1            end -= 1        return ''.join(s)`

I saw on the discussion board that some people were getting faster runtimes by using a case statement instead of a set for vowel look-up. I'm not sure whether that's gaming the Leetcode online judge or whether it's actually faster than using the hash function via Set look-up. Will probably depend on different languages and their implementations.

Runtime complexity: `O(n)`.

Spacetime complexity: `O(1)`.

### Isomorphic Strings

Problem: Given two strings, check if they are isomorphic.

I.e., do they have the same pattern of letters. E.g., `zoo` matches `bee`. (`011` -> `011`).

I wanted to compare some integer lists representing string patterns.

`class Solution(object):    def isIsomorphic(self, s, t):        """        :type s: str        :type t: str        :rtype: bool        """        count = 0        letters = dict()                s_list = []        for i in s:            if i not in letters:                count += 1                letters[i] = count            s_list.append(letters[i])                    count = 0        letters = dict()                t_list = []        for i in t:            if i not in letters:                count += 1                letters[i] = count            t_list.append(letters[i])                    return s_list == t_list`

While linear in runtime, this solution felt a little clumsy to me. However, the only improvement that I found on the forums was to use arrays instead of look-up tables since the test cases were all ASCII letters.

Runtime complexity: `O(n)`.

Space complexity: `O(n)`.

### Reverse Words in a String

Problem: Reverse the words in a string, remove leading and trailing spaces, have no more than one space between words.

I was surprised to see that this is classed as Medium difficulty but I suppose with the space-character edge cases, if I were not using Python (which, also, is fantastic at string manipulation), it would be a little harder.

`class Solution(object):    def reverseWords(self, s):        """        :type s: str        :rtype: str        """        return ' '.join(s.split()[::-1])`

A pretty neat one-liner. `s.split()` takes care of all space-character edge cases for us!

My (undeservedly) fastest runtime percentile yet: 99.17th. The fastest solution available returns early for an empty string which is a small optimization.

Runtime complexity: `O(n)`.

Spacetime complexity: `O(n)`.