June 9, 2019
Introduction
It is the algorithm I like to learn as many solutions as I can. I also think about how to use this algorithm in mock interview for me to explore the algorithm as much as I can in future interviews on interviewing.io as a mock interviewer.
Case study
Here is one elegant solution I like to explore, learn and write one.
I wrote C# code based on the above post. Here is the link. Also, I did case study on "AAB", and then I wrote a solution to show all tiles as well. Here is the link.
I also copy and paste the content here.
It is challenging job to write a case study, and then figure out how to interpret the code written in such an elegant solution, the solution post is here. I like to share the solution with case study "AAB" and extra output to show depth first search all result with "AAB" study case.
Case study "AAB"
I like to write down some explanation based on case study "AAB". I am just a learner with some curiousity. Follow me and let me know if I miss the important things in my analysis.
case study: "AAB"
count: A -> 2, B->1
length 1: "A", "B"
length 2:
For "A":
count: A->1, B->1
We can still pick either A, or B
So we have "AA,"AB"
For "B":
count: A->2, B->0
We can only pick A
So we have "BA"
The answer is 8. How to ensure uniqueness?
set prefix = ""
dfs("AAB") -> two distinct chars, 'A', 'B', each one sum variable increment one; related to tile: prefix + "A", prefix + "B".
For 'A' case, next step is to calculate dfs("AB"), what ever it has, the string should be prefixed with "A".
For 'B' case, next step is to calculate dfs("AA"), what ever it has, the string should be prefixed with "B".
count: A -> 2, B->1
length 1: "A", "B"
length 2:
For "A":
count: A->1, B->1
We can still pick either A, or B
So we have "AA,"AB"
For "B":
count: A->2, B->0
We can only pick A
So we have "BA"
The answer is 8. How to ensure uniqueness?
set prefix = ""
dfs("AAB") -> two distinct chars, 'A', 'B', each one sum variable increment one; related to tile: prefix + "A", prefix + "B".
For 'A' case, next step is to calculate dfs("AB"), what ever it has, the string should be prefixed with "A".
For 'B' case, next step is to calculate dfs("AA"), what ever it has, the string should be prefixed with "B".
So the output of search result is the following:
"A"
"AA"
"AAB"
"AB"
"ABA"
"B"
"BA"
"BAA"
"A"
"AA"
"AAB"
"AB"
"ABA"
"B"
"BA"
"BAA"
Next step
Since the algorithm is to ask the total number of tile possibilities, we do not need to know all tiles. I mark those lines of code added just to be easily followed.
The code with debugging info
I made a few changes based on study code, so that it is easy to tell statement "sum++", what is the tile content.
I made a few changes based on study code, so that it is easy to tell statement "sum++", what is the tile content.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _5087_Letter_tile_possibilities
{
class Program
{
static void Main(string[] args)
{
NumTilePossibilities("AAB");
}
/// <summary>
/// June 9, 2019
/// study code:
/// https://leetcode.com/problems/letter-tile-possibilities/discuss/308284/Concise-java-solution
/// </summary>
/// <param name="tiles"></param>
/// <returns></returns>
public static int NumTilePossibilities(string tiles)
{
int[] count = new int[26];
foreach (var item in tiles)
{
count[item - 'A']++;
}
var all = new List<string>();
return depthFirstSearch(count, "", all);
}
/// <summary>
/// case study: "AAB"
/// count: A -> 2, B->1
/// length 1: "A", "B"
/// length 2:
/// For "A":
/// count: A->1, B->1
/// We can still pick either A, or B
/// So we have "AA,"AB"
/// For "B":
/// count: A->2, B->0
/// We can only pick A
/// So we have "BA"
/// Questions:
/// 1. uniqueness - not duplicated one, how to ensure uniqueness
/// 2.
/// </summary>
/// <param name="numbers"></param>
/// <returns></returns>
private static int depthFirstSearch(int[] numbers, string prefix, List<string> tiles)
{
int sum = 0;
for(int i = 0; i < 26; i++)
{
if(numbers[i] == 0)
{
continue;
}
sum++;
/* determine what is tile to be added*/
char toChar = Convert.ToChar('A' + i);
var nextPrefix = prefix + toChar.ToString();
tiles.Add(nextPrefix);
/**/
numbers[i]--;
sum += depthFirstSearch(numbers, nextPrefix, tiles);
numbers[i]++;
}
return sum;
}
}
}
