Hiking around HackerRank — 08
12/14/2020
Note:
- All problems are published by HackerRank, credit to HackerRank
- The solutions are coded by myself, and open source just for study.
Valid Username Regular Expression
Theoretically, this is not difficult. We just need to make sure:
- The valid input should start with an alphabet;
- The length should between 8 and 30 (include 8 but not include 30)
Thus, the regular expression should be like this: “^[aA-zZ]\\w{7,29}$”
To clarify, we can refer to the discussion forum: “^” means the start of the character, which should be [aA-zZ]. The word (w) length should be {7, 29} to the end of the word($). Thanks to Tommy Mertell for the explanation!
The code is as below:
import java.util.Scanner;
class UsernameValidator {
/*
* Write regular expression here.
*/
public static final String regularExpression = "^[aA-zZ]\\w{7,29}$";
}
public class Solution {
private static final Scanner scan = new Scanner(System.in);
public static void main(String[] args) {
int n = Integer.parseInt(scan.nextLine());
while (n-- != 0) {
String userName = scan.nextLine();
if (userName.matches(UsernameValidator.regularExpression)) {
System.out.println("Valid");
} else {
System.out.println("Invalid");
}
}
}
}The strange thing is: HackerRank said I solved this problem, yet test 0 failed. How do you think about it? Anyway, I need to move on.
Tag Content Extractor
I think I tried to solve this problem before, but doubtlessly I failed. Now, let’s solve it!
The idea is not difficult to understand: extract the content between the tags. Therefore, we need a regular expression to filter those elements. Refer to the discussion board, “<(.+)>” matches the start of the tag, “</\\1>” matches the end of the tag, and “([^<]+)” matches the content between them. Thanks to @RodneyShag for the great explanation!
The code is as below:
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int testCases = Integer.parseInt(in.nextLine());
while(testCases>0){
String line = in.nextLine();
//Write your code here
boolean isMatch = false;
Pattern r = Pattern.compile("<(.+)>([^<]+)</\\1>");
Matcher m = r.matcher(line);
while(m.find()){
isMatch = true;
System.out.println(m.group(2));
}
if (!isMatch){
System.out.println("None");
}
testCases--;
}
in.close();
}
}And it succeeded this time! Woo!
Java Stack
It’s my first time to work on data structure seriously. Refer to Wikipedia, the stack is a LIFO (last in, first put) abstract data type that serves as a collection of elements. It supports push (add an element to the collection) and pop (remove the last element that was added). (Wikipedia)
Let’s have a look at this question: it is not so difficult to solve this problem with regular expression instead of the stack. So, let’s have a try:
Refer to Java replace all square brackets in a string on StackOverflow, we can easily replace “()”, “[]”, and “{}” with empty space in Java. My initial try was as below:
import java.util.*;
class Solution{
public static void main(String []argh)
{
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String input=sc.next();
//Complete the code
if(input != (input = input.replaceAll("\\(\\)|\\[\\]|\\{\\}", ""))){
System.out.println(input.isEmpty());
}
}
}
}Unfortunately, it failed. What happened?
I checked the discussion board and found our track was almost correct, yet we can use a “while” (not loop) to indicate the condition of this problem. The modified code is as below:
import java.util.*;
class Solution{
public static void main(String []argh)
{
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String input=sc.next();
//Complete the code
while (input != (input = input.replaceAll("\\(\\)|\\[\\]|\\{\\}", "")));
System.out.println(input.isEmpty());
}
}
}And it succeeded! However, may we try to solve it with the knowledge of data structure?
Refer to the discussion forum, we can check the first element of the input by using “peek” and remove and return the top element with “pop”. Also, the operator can push an element to the stack with “push”. Sounds easy, right? Let’s have a try:
import java.util.*;
class Solution{
public static void main(String []argh)
{
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String input=sc.next();
Stack<Character> s = new Stack<>();
for (int i = 0; i < input.length(); i++) {
if (!s.isEmpty()) {
switch(input.charAt(i)) {
case '}' : if (s.peek() == '{') {
s.pop();
} break;
case ']' : if (s.peek() == '[') {
s.pop();
} break;
case ')' : if (s.peek() == '(') {
s.pop();
} break;
default: s.push(input.charAt(i));
}
} else {
s.push(input.charAt(i));
}
}
System.out.println(s.isEmpty());
}
}
}Fortunately, it worked! Thanks to Kathryn Hodge for sharing her idea on the discussion board!
The benefit of using a stack should be lowering time complexity. However, I’m not a master of time complexity, but I hope we may have a chance to take about it. To be honest, I’m not sure if this is cool enough to use the stack in this way, but I feel good to move on!
Conclusion:
Although I think I’m making progresses, the improvement is still trivial. Maybe that’s because the difficulty of the problems is increasing, but I believe we can do better.
This is my repo. Hope it helps!
References:
Valid Username Regular Expression, HackerRank, retrieved from https://www.hackerrank.com/challenges/valid-username-checker/problem
Valid Username Regular Expression, HackerRank Discussion, retrieved from https://www.hackerrank.com/challenges/valid-username-checker/forum
Tag Content Extractor, HackerRank, retrieved from https://www.hackerrank.com/challenges/tag-content-extractor/problem
Java Stack, HackerRank, retrieved from https://www.hackerrank.com/challenges/java-stack/problem
Stack, Wikipedia, retrieved from https://en.wikipedia.org/wiki/Stack
Java replace all square brackets in a string, StackOverflow, retrieved from https://stackoverflow.com/questions/14442162/java-replace-all-square-brackets-in-a-string
Java Stack, Hacerk Rank, retrieved from https://www.hackerrank.com/challenges/java-stack/forum
