Long Pressed Name, by Leetcode

-
Problem: https://leetcode.com/problems/long-pressed-name/description/

Your friend is typing his name into a keyboard.  Sometimes, when typing a character c, the key might get long pressed, and the character will be typed 1 or more times.
You examine the typed characters of the keyboard.  Return True if it is possible that it was your friends name, with some characters (possibly none) being long pressed.
Recursive solution, with simple base case, trimming based on the first chars equality (or inequality), optimization based on the typed string containing the name, and finally the recursion moving name once or keeping it as it is. Key optimization that made it pass was this. Cheers, Boris

public class Solution
{
public bool IsLongPressedName(string name, string typed)
{
if (String.IsNullOrEmpty(name) && String.IsNullOrEmpty(typed)) return true;
if (String.IsNullOrEmpty(name) || String.IsNullOrEmpty(typed)) return false;
if (name[0] != typed[0]) return false;
if (typed.Contains(name)) return true;
return IsLongPressedName(name, typed.Substring(1)) || 
                                   IsLongPressedName(name.Substring(1), typed.Substring(1));
}
}

Comments

  1. TarasNovember 23, 2018 at 8:49 PM

    Very concise solution, Boris! The complexity can be improved though, since your solution has a lot of overlapping problems and is somewhat similar to a naive implementation of wildcard matching problem. In this particular case though, a single scan of both strings is enough. We can use 2 indices pointing at positions inside of name and typed - if characters these indices point to are not the same, we can immediately tell that it's not a result of a long press, but if they are, we can count how many repetitions we have for each and the typed string can only be a result of a long press if this number is <= in name string. The implementation of this idea in C++ is somewhat longer but hopefully still easy to follow is below:

    class Solution {
    public:
    bool isLongPressedName(const string& name, const string& typed) {
    if (name.empty() != typed.empty()) return false;
    if (name.empty() && typed.empty()) return true;
    int right = 0;
    for (int i = 0; i < name.size(); ) {
    if (name[i] != typed[right]) return false;
    int name_count = 1;
    int j;
    for (j = i + 1; j < name.size() && name[j-1] == name[j]; ++j) {
    name_count += 1;
    }
    i = j;
    int typed_count = 1;
    for (j = right + 1; j < typed.size() && typed[j-1] == typed[j]; ++j) {
    typed_count += 1;
    }
    right = j;
    if (name_count > typed_count) return false;
    }
    return true;
    }
    };

    ReplyDelete
  2. Boris VasilenkoNovember 25, 2018 at 2:10 PM

    So true, after I wrote it I realized that my solution is actually exponential and I thought exactly about yours. Very nice!!

    ReplyDelete
    Replies
    1. TarasNovember 25, 2018 at 2:16 PM

      well, as long as it's accepted it's legit :) It's always best to start with an obviously correct solution and if necessary optimize it and your solution is definitely more readable, although I believe the iterative solution could be significantly improved by using missing abstractions like takeWhile from Haskell. In any case it's always great to compare solutions with yours, so please keep them coming :)

      Delete

Post a Comment

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more