term1 Definition1term2 Definition2term3 Definition3
Please sign in to your Google account to access your documents:
Details to confirm:
* Is the string an ASCII string or Unicode.
* Suppose for simplicity maximum length string =128 characters.
- Create a 128 length boolean array.
- Loop through the string getting the char value at the specified index i and using it like the index in the boolean array.
- If this value is TRUE, it means it is the second time you see this character, so you can immediately return FALSE.
- After that, do the value TRUE.
- When the loop finishes, return TRUE
The time complexity = O(n) = O(128) = O(1) The space complexity is O(1)
Given two strings, write a method to decide if one is a permutation of the other.
* Is comparison case sensitive ?
* Is whitespace significant ?
We just need to compare the sorted versions of the strings. It's clean, simple and easy to understand but it's NOT optimal. (Use toCharArray() and java.util.Arrays.sort)
- If the strings don't have the same length, return FALSE.
- Create a 128 length int array.
- Loop through the first string and count the number of each char storing it in the int array (intArray[str1.charAt(i)]++)
- Loop through the second string, but this time decrease by 1 each occurrence of the char (intArray[str1.charAt(i)]--). After that, immediately check if the number is negative. In this case return FALSE.
- When the second loop finishes, return TRUE.
The time complexity = O(S1 + S2) = O(256) = O(1)The space complexity is O(1)
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. (Note: if implementing in Java, please use a character array so that you can perform this operation in place)
Approach: Working backward
Details to confirm or assume:
* Assume string has sufficient free space at the end.
* Because immutability of String in Java, we will use a char array. At the end, suppose we have a function called charArrayToString.
- Convert the String to a char array (str.toCharArray)
- Get the findLastCharacter going backward in a for loop. Adding one to the result we'll get the trueLength.
- The algorithm employs a two-scan approach. In the first scan, we count the number of spaces using trueLength. The index would be index = trueLength + spaceCount * 2
- In the second pass, which is done in reverse order, we actually edit the string. When we see a space, we replace it with %20. If there is no space, then we copy the original character.
Need help typing ? See our FAQ (opens in new window)
Please sign in to create this set. We'll bring you back here when you are done.
Discard Changes Sign in
Please sign in to add to folders.
Sign in
Don't have an account? Sign Up »
You have created 2 folders. Please upgrade to Cram Premium to create hundreds of folders!