Showing posts from March, 2018

Unique Morse Code Words, by LeetCode

Problem tonight is this one: International Morse Code defines a standard encoding where each letter is mapped to a series of dots and dashes, as follows:  "a" maps to  ".-" ,  "b"  maps to  "-..." ,  "c"  maps to  "-.-." , and so on. For convenience, the full table for the 26 letters of the English alphabet is given below: [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."] Now, given a list of words, each word can be written as a concatenation of the Morse code of each letter. For example

Letter Case Permutation, by LeetCode

A relatively easy problem, by LeetCode: : Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string.  Return a list of all possible strings we could create. Examples: Input: S = "a1b2" Output: ["a1b2", "a1B2", "A1b2", "A1B2"] Input: S = "3z4" Output: ["3z4", "3Z4"] Input: S = "12345" Output: ["12345"] Given that Len(S)<=12, a simple recursive solution will do it. I usually use the same recipe for such a problem: I usually prefer to have an internal method which does the actual processing,  doesn't return anything, and passes the "return value" by reference There is a string which is the "current" working string. This will be the candidate to be added to the retVal The recursion is controlled based on the position (inde

Strong Password, by HackerRank

It has been a while since I solved a HackerRank problem (they have not been posting new problems, now apparently there is a wave of new ones coming), here it is : There isn't a lot to "optimize" in the solution for this problem: pretty much just follow the 5 points mentioned in the problem description. There is some minor math to worry about, but other than that this is the kind of problem whose description is telling you how to solve it (just like those songs whose lyrics tell you how to dance to them ;)). Code is below, many hugs, Boris. using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { static int minimumNumber(int n, string password) { // Return the minimum number of characters to make the password strong if (password.Length != n) return 0; string numbers = "0123456789"; string lower_case = "abcdefghijklmno

Reverse String II - LeetCode

A very error-prone problem: Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original. Example: Input: s = "abcdefg", k = 2 Output: "bacdfeg" The problem description is describing the algorithm, but the pain in the lower back is to get the details coded up well. First build a Reverse function (private) to facilitate your life. Then try to follow the algorithm in the description as close as possible. Then submit it, and go to sleep. Good night! Boris public class Solution { public string ReverseStr(string s, int k) { string retVal = ""; for (int from = 0; from < s.Length;

Delete Operation for Two Strings, by LeetCode: a variation of edit distance via DP

Problem is this one: : Given two words  word1  and  word2 , find the minimum number of steps required to make  word1  and  word2  the same, where in each step you can delete one character in either string. Example 1: Input: "sea", "eat" Output: 2 Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea". This is a variation of the classic String Edit Distance  problem, whose solution is one of the iconic Dynamic Programming solutions. Knowing that this is a variation, all it is needed is a paper (or whiteboard) and try few variations to understand the logic: having a distance matrix where each element distance[i,j] represents the min distance when comparing word1[0..i] and word2[0..j]. The fun part is to figure out the logic of how to update distance[i,j] depending on whether word1[i] is equal or not to word2[j]. You