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 = 0end = len(s)-1while not start >= end:if s[start] not in vowels:start += 1continueif s[end] not in vowels:end -= 1continues[start], s[end] = s[end], s[start]start += 1end -= 1return ''.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 = 0letters = dict()s_list = for i in s:if i not in letters:count += 1letters[i] = counts_list.append(letters[i])count = 0letters = dict()t_list = for i in t:if i not in letters:count += 1letters[i] = countt_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.