Given two strings s0 and s1, return whether you can obtain s1 by removing 1 letter from s0.
Example 1
Input
s0 = “hello”
s1 = “hello”
Output
falseExample 2
Input
s0 = “hello”
s1 = “helo”
Output
true
Remove One Letter Algorithm
First, we need to compare the lengths of two strings, if the s0 is not one length more than s1, we simply can’t construct s1 from removing one letter from s0. Then we check the letter by letter once we find a difference, we need to compare the rest (using substr) of s1[i:] and s0[i+1:] to see if they are equal.
1 2 3 4 5 6 7 8 9 10 11 | bool removeOneLetter(string s0, string s1) { if (s0.size() != s1.size() + 1) { return false; } for (int i = 0; i < s1.size(); ++ i) { if (s1[i] != s0[i]) { return s1.substr(i) == s0.substr(i + 1); } } return true; } |
bool removeOneLetter(string s0, string s1) {
if (s0.size() != s1.size() + 1) {
return false;
}
for (int i = 0; i < s1.size(); ++ i) {
if (s1[i] != s0[i]) {
return s1.substr(i) == s0.substr(i + 1);
}
}
return true;
}The time complexity is O(N) as we are iterating N loops at most. The space complexity is O(1) constant. See also: Teaching Kids Programming – Remove One Letter
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
262 wordsloading...
Last Post: Algorithms to Convert Binary Linked List to Integer
Next Post: Single Core CPU Scheduling Algorithm by Using a Priority Queue
