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.
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.
Problem: Given two strings, check if they are isomorphic.
I.e., do they have the same pattern of letters. E.g.,
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.
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.
Comments or questions? I enjoy talking with readers over email.