Created
September 26, 2017 21:44
-
-
Save jianminchen/17b5f82a99b0ce512f798e4432f2eef6 to your computer and use it in GitHub Desktop.
Leetcode 76 smallest substring - fix the issue like missing Dictionary.ContainsKey checking before visit the dictionary
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Diagnostics; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace substring_practice | |
{ | |
// []'x','y','z'] - substring containing all characters | |
// find smallest -> minimum length | |
//linear scan string -> O(n), visit char once | |
// left point -> current point -> | |
// index = 0 | |
// x -> hashmap -> Dictinary<char, int> 'x', 1 , 'y' 1, 'z' 1 | |
// x -> 'x' 1 - 1 -> 0 , no need | |
// left 0 -> | |
// y -> 'y' 1 -1 -> 0 -> variable to help to check if > 0 | |
// y -> 'y' 0 - 1 -> -1 | |
// z -> 'z' 1 - 1 -> 0 find word -> left 0, index = 3, "xyyz", length = 4, minimum | |
// left point -> x -> +1, need one x , value 1 > 0 | |
// go back step 18 or 19 | |
class Program | |
{ | |
static void Main(string[] args) | |
{ | |
var testResult = GetShortestUniqueSubstring(new char[]{'x','y','z'}, "byazx"); | |
Debug.Assert(testResult.CompareTo("yazx") == 0); | |
} | |
/// <summary> | |
/// 9/26/2017 | |
/// Work on left pointer while loop issue | |
/// test case: xxxyz, unqiue array 'x', 'y','z' | |
/// | |
/// </summary> | |
/// <param name="arr"></param> | |
/// <param name="str"></param> | |
/// <returns></returns> | |
public static string GetShortestUniqueSubstring(char[] arr, string str) | |
{ | |
// your code goes here | |
if (arr == null || arr.Length == 0) | |
{ | |
return ""; | |
} | |
// assume that arr is not empty | |
if (str == null || str.Length == 0) | |
{ | |
return ""; | |
} | |
// put arr to the dictionary | |
var map = new Dictionary<char, int>(); | |
foreach (var item in arr) | |
{ | |
map.Add(item, 1); | |
} | |
var needChars = arr.Length; // 'xyz' - 3, var match = needChars == 0 | |
// iterate the string and find match, and also keep track of minimum | |
var left = 0; | |
var length = str.Length; | |
var smallestLength = length + 1; // | |
var smallestSubstring = ""; | |
for (int index = 0; index < length; index++) // byazx | |
{ | |
var visit = str[index]; | |
// x - 1 | |
var inMap = map.ContainsKey(visit); | |
var needOne = inMap && map[visit] > 0; // add checking contains | |
if (inMap) | |
{ | |
map[visit]--; | |
} | |
if (needOne) | |
{ | |
needChars--; // take x off | |
} | |
var findMatch = needChars == 0; | |
if (!findMatch) | |
{ | |
continue; | |
} | |
// move left point forward - while loop | |
while (left <= index && map.ContainsKey(str[left]) && map[str[left]] < 0) | |
{ | |
var removeChar = str[left]; | |
// update the variable needChars xx -1 | |
map[removeChar]++; | |
left++; | |
} | |
var currentLength = index - left + 1; | |
var findSmallerOne = currentLength < smallestLength; | |
if (findSmallerOne) | |
{ | |
smallestLength = currentLength; | |
smallestSubstring = str.Substring(left, currentLength); | |
needChars++; | |
map[str[left]]++; // bug found for current test case | |
left = left + 1; | |
} | |
} | |
// edge case | |
if (smallestLength == length + 1) | |
{ | |
return ""; | |
} | |
else | |
{ | |
return smallestSubstring; | |
} | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment