Created
August 28, 2016 08:01
-
-
Save jianminchen/12e7c74b57c5780a069b0e9df66f77c3 to your computer and use it in GitHub Desktop.
world code sprint #6 - abbreviation - https://www.hackerrank.com/contests/world-codesprint-6/challenges/abbr - score 40 out of 40
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.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace Abbreviation | |
{ | |
class Program | |
{ | |
static void Main(string[] args) | |
{ | |
//test(); | |
hackRank(); | |
} | |
public static void hackRank() | |
{ | |
int queries = Convert.ToInt32(Console.ReadLine().Trim()); | |
for (int i = 0; i < queries; i++) | |
{ | |
string s1 = Console.ReadLine(); | |
string s2 = Console.ReadLine(); | |
Console.WriteLine((CanConvert(s1,s2)? "YES":"NO")); | |
} | |
} | |
public static void test() | |
{ | |
string s1 = "daBcd"; | |
string s2 = "ABC"; | |
bool res = CanConvert(s1, s2); | |
} | |
public static bool CanConvert(string s1, string s2) | |
{ | |
int[] lowerArr1 = new int[26]; | |
int[] upperArr1 = new int[26]; | |
int[] arr2 = new int[26]; | |
if (s1 == null || s1.Length == 0) | |
return false; | |
foreach(char c in s1.Trim()) | |
{ | |
int no = c - 'a'; | |
bool isLower = isLowerCase(no); | |
if (isLower) | |
lowerArr1[no]++; | |
else | |
upperArr1[c - 'A']++; | |
} | |
foreach (char c in s2.Trim()) | |
{ | |
arr2[c - 'A']++; | |
} | |
// preprocessing | |
// check s1 and s2 count of char from A to Z | |
for(int i = 0; i < 26; i++) | |
{ | |
int total = lowerArr1[i] + upperArr1[i]; | |
if (total < arr2[i] || upperArr1[i] > arr2[i]) | |
return false; | |
} | |
int index1 = 0; | |
int index2 = 0; | |
while( index2 < s2.Length ) | |
{ | |
if (index1 >= s1.Length) | |
return false; | |
char c1 = s1[index1]; | |
char c2 = s2[index2]; | |
int no = (c1-'a'); | |
bool isLower = no >= 0 && no < 26; | |
if (!isLower) | |
no = c1 - 'A'; | |
if((c1 == c2) || (c1 - 'a') == (c2 - 'A')) | |
{ | |
// if isLower, then discuss skip no is available or not | |
bool convertLowerToUpper = isLower && (arr2[no] > upperArr1[no]); | |
bool bothUpper = c1 == c2; | |
if (bothUpper || convertLowerToUpper) | |
{ | |
index2++; | |
arr2[no]--; | |
} | |
} | |
index1++; | |
if (isLower) | |
lowerArr1[no]--; | |
else | |
upperArr1[no]--; | |
if(!isOk(lowerArr1, upperArr1, arr2, no)) | |
return false; | |
} | |
return true; | |
} | |
public static bool isLowerCase(int no) | |
{ | |
return no >= 0 && no < 26; | |
} | |
/* | |
* test case: | |
* s1 = "aA", s2="A" - ok | |
* s1 = "AA", s2="A" - false | |
*/ | |
public static bool isOk(int[] lowerArr1, int[] upperArr1, int[] arr2, int index) | |
{ | |
int total = lowerArr1[index] + upperArr1[index]; | |
if (total < arr2[index] || upperArr1[index] > arr2[index]) | |
return false; | |
return true; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Hi there,
Your solution doesnt work for cases 12, 13 and 14.
Maybe the assignment changed since you programmed it, but now it doesnt work. I used my solution in python and also cannot make the 12,13 and 14 work.