Thursday, January 21, 2021

Leetcode discuss: 1576. Replace All ?'s to Avoid Consecutive Repeating Characters

 Jan. 21, 2021

Here is the link. 

First practice - C# - "abc" - 20+ minutes

Jan. 21, 2021
Introduction
It is my first algorithm in Microsoft mock onsite. It took me over 20 minutes to calm down, and I like to simplify my solution, avoid so many if case.

Case study
"abc" is chosen to replace all '?' chars, since there is at most two neighbors for any '?' char, it is working to find one char left after removing those two neighbor chars.

I thought about cases if there is left neighbor or right neighbor, if it is '?' or not. I think that it is better to remove two neighbor chars, first one left will be chosen.

It is my way to replace. I wish that I can solve it in less than 10 minutes. But in reality, I took two days break to practice mock onsite. I tried to learn one hard level in my previous one. I have hard time to focus and think quickly.

The following code passes online judge.

public class Solution {
    public string ModifyString(string s) {
        if(s == null || s.Length == 0)
        {
            return "";
        }               
       
        var arr = s.ToCharArray(); 
        
        var length = s.Length; 
        
        for(int i = 0; i < length; i++)
        {
            var current = s[i];
            var empty = current == '?';
         
            var replaced = new HashSet<char>("abc".ToCharArray());
            
            if(!empty)
            {
                continue; 
            }
            
            if(i > 0)
            {
                replaced.Remove(arr[i - 1]);
            }
            
            if(i < length - 1)
            {
                replaced.Remove(arr[i + 1]);
            }
            
            arr[i] = replaced.ToList()[0];
        }
        
        return new string(arr); 
    }
}

No comments:

Post a Comment