Here's a set of problems for the class. Exploiring strings.
Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?
Hints:
- Try a hash table
- Can you solve it in
O(N log N)time? What might a solution like that look like? - Could a bit vector be useful?
Given two strings, write a method to decide if one is a permutation of the other.
Hints:
- Describe what it means for two strings to be permutations of each other. Now, look at that definition you provided. Can you check the strings against that definition?
- There is one solution that is
O(N log N)time. Another solution uses some space, but isO(N)time. - Could a hash table be useful?
- Two strings that are permutations should have the same characters, but in different orders. Can you make the orders the same?
Write a method to replace all spaces in a string with %20. You may assume that the string has sufficient space at the end to hold the additional characters, and that you are given the "true" length of the string.
Assume that you have mutable strings. It's not in many languages but you always can turn a string into an array of chars.
- It's often easiest to modify strings by going from the end of the string to the beginning.
- You might find you need to know the number of spaces. Can you just count them?
Problems and hints could be found in "Cracking the coding interview" by Gayle MacDowell.