Letter Case Permutation, by LeetCode

-
A relatively easy problem, by LeetCode: https://leetcode.com/problems/letter-case-permutation/description/:

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 (index) being worked on right now. When it goes past (or equal, sure..) the length of S, stop
  • Call recursively for the current index irrespective of the character being processed
  • Then deal with the cases for either lower or upper case. Swap them appropriately
That should do it. Code is below, cheers, Marcelo


public class Solution

{
public IList<string> LetterCasePermutation(string S)
{
IList<string> retVal = new List<string>();
LetterCasePermutationInternal("", 0, S, ref retVal);
return retVal;
}

private void LetterCasePermutationInternal(string current, int pos, string S, ref IList<string> retVal)
{
if (pos == S.Length)
{
retVal.Add(current);
return;
}
LetterCasePermutationInternal(current + S[pos].ToString(), pos + 1, S, ref retVal);
if (S[pos] >= 'a' && S[pos] <= 'z')
{
LetterCasePermutationInternal(current + S[pos].ToString().ToUpper(), pos + 1, S, ref retVal);
}
else if (S[pos] >= 'A' && S[pos] <= 'Z')
{
LetterCasePermutationInternal(current + S[pos].ToString().ToLower(), pos + 1, S, ref retVal);
}
}
}

Comments

  1. TarasMarch 21, 2018 at 11:07 PM

    nicely done! Python version is a bit shorter (1 liner) :)

    class Solution:
    def letterCasePermutation(self, S):
    return [head + permutation for head in ((S[0].lower(), S[0].upper()) if S[0].isalpha() else S[0]) for permutation in self.letterCasePermutation(S[1:])] if S else [""]

    Or for fans of Haskell naming style:

    return [x + xs for x in ((S[0].lower(), S[0].upper()) if S[0].isalpha() else S[0]) for xs in self.letterCasePermutation(S[1:])] if S else [""]

    Cheers,
    Taras

    ReplyDelete

Post a Comment

Popular posts from this blog

Advent of Code - Day 6, 2024: BFS and FSM

-
Image
To solve this Advent of Code (parts 1 and 2), I used Breadth-First Search (BFS) to keep moving the guard as well as Finite State Machine (FSM) to control the directions. This solves part 1 easily. Part 2 can be solved using the same technique, takes a little longer since you need to try every empty cell, but it eventually does the trick (takes a min or so). Code is down below, cheers, ACC. Day 6 - Advent of Code 2024 using System.IO; using System.Collections; using System; using System.Text; using System.Text.RegularExpressions; using System.ComponentModel.DataAnnotations; Process2(); void Process() { string fileName = "input.txt"; FileInfo fileInfo = new FileInfo(fileName); StreamReader sr = fileInfo.OpenText(); List map = new List (); int startRow = 0; int startCol = 0; while (!sr.EndOfStream) { string line = sr.ReadLine().Trim(); map.Add(new StringBuilder(line)); int indexStart = line.IndexOf('^'); ...
Read more

Golang vs. C#: performance characteristics (simple case study)

-
Image
This is an interesting example to study the performance characteristics of Golang compared to C# for a very particular case (not generalized though).  The same code was written in C# and Golang (literally translated from one to the other). Below you'll be able to see the source code for both. The problem is a simple post-order DFS in a tree-like graph. The code in C# times out (TLE = Time Limited Exceeded). The code in Golang not only works but beats 100% of the other Golang submissions. Take a look the image below: Some potential reasons for the performance gains from Go in this particular example are: 1. Language and Runtime Differences:    Go is compiled directly to machine code, while C# typically runs on a virtual machine (CLR).    Go has a simpler runtime with less overhead compared to the .NET runtime.    Go's garbage collector is designed for low latency, which can lead to better performance in some scenarios. 2. Data Structures:    G...
Read more

Advent of Code - Day 7, 2024: Backtracking and Eval

-
Image
Problem today requires backtracking and eval (evaluating a mathematical expression in the format of a string). Glad that it used a left-2-right evaluation, makes for an easy parsing and not overly complicated evaluation function. Code is down below for parts 1 and 2. Cheers, ACC. Day 7 - Advent of Code 2024 using System.IO; using System.Collections; using System; using System.Text; using System.Text.RegularExpressions; using System.ComponentModel.DataAnnotations; Process2(); void Process() { string fileName = "input.txt"; long retVal = 0; FileInfo fileInfo = new FileInfo(fileName); StreamReader sr = fileInfo.OpenText(); while (!sr.EndOfStream) { string line = sr.ReadLine().Trim(); string[] parts1 = line.Split(':'); long target = Int64.Parse(parts1[0]); string[] numbers = parts1[1].Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries); if (TryAll1(numbers, target, "", 0)) r...
Read more