Word Pattern

It seems to me that LeetCode (https://leetcode.com/) has more complex challenges than HackerRank (https://www.hackerrank.com/domains?h_r=logo). Their approach to testing the solutions is different. They not only test for correctness but they also check for execution time.

In the next few weeks will concentrate in solving challenges from LeetCode. I will also try to get to weekend competitions if they are relatively early in the day (I am a morning person).

If interested take a look at the requirements for this challenge using the following link:  https://leetcode.com/problems/word-pattern/

Following is a screen capture of the Eclipse IDE console using the sample and a few more test cases:

8

abba

dog cat cat dog

abba

dog cat cat fish

aaaa

dog cat cat dog

abba

dog dog dog dog

aba

dog cat dog dog

bab

dog cat

abcabc

dog cat mouse dog cat mouse

abccba

dog cat mouse mouse cat dog

main <<< N: 8

main <<< pattern ==>abba<==

main <<< str ==>dog cat cat dog<==

main <<< match: true

main <<< pattern ==>abba<==

main <<< str ==>dog cat cat fish<==

main <<< match: false

main <<< pattern ==>aaaa<==

main <<< str ==>dog cat cat dog<==

main <<< match: false

main <<< pattern ==>abba<==

main <<< str ==>dog dog dog dog<==

main <<< match: false

main <<< pattern ==>aba<==

main <<< str ==>dog cat dog dog<==

main <<< match: false

main <<< pattern ==>bab<==

main <<< str ==>dog cat<==

main <<< match: false

main <<< pattern ==>abcabc<==

main <<< str ==>dog cat mouse dog cat mouse<==

main <<< match: true

main <<< pattern ==>abccba<==

main <<< str ==>dog cat mouse mouse cat dog<==

main <<< match: true

My solution including my test code written in Java follows:

import java.util.LinkedHashMap;

import java.util.Scanner;

public class Solution {

/*

*

*/

static boolean wordPattern(String pattern, String str) {

// **** ****

String[] ss = str.split(” “);

// **** lengths should match ****

if (pattern.length() != ss.length) {

return false;

}

// **** instantiate a hash map with the characters and strings ****

LinkedHashMap<Character, String> map = new LinkedHashMap<>();

// **** traverse the pattern ****

for (int i = 0; i < pattern.length(); i++) {

// **** ****

char c = pattern.charAt(i);

// **** c has already been assigned ****

if (map.containsKey(c)) {

String val = map.get(c);

if (!val.equals(ss[i])) {

return false;

}

}

// **** c has not been assigned ****

else {

// **** check if the word has already been assigned ****

if (map.containsValue(ss[i])) {

return false;

}

// **** insert the pair into the map ****

map.put(c, ss[i]);

}

}

// **** ****

return true;

}

/*

* Test code.

*/

public static void main(String[] args) {

// **** open the scanner ****

Scanner sc = new Scanner(System.in);

// **** read the number of test cases ****

int N = sc.nextInt();

System.out.println(“main <<< N: ” + N);

sc.nextLine();

// **** loop once per test case ****

for (int n = 0; n < N; n++) {

// **** read the pattern ****

String pattern = sc.nextLine();

System.out.println(“main <<< pattern ==>” + pattern + “<==”);

// **** read the string ****

String str = sc.nextLine();

System.out.println(“main <<< str ==>” + str + “<==”);

// **** determine if there is a pattern ****

System.out.println(“main <<< match: ” + wordPattern(pattern, str) + “\n”);

}

// **** close the scanner ****

sc.close();

}

}

After solving the challenge I was going to optimize the approach using arrays. I decided that it would be better to continue with the next challenge. While visiting the LeetCode site I noticed that the contest for this weekend is in the evening :o( Will wait to register for the next one starting in the morning.

If you have comments on this or any other post in this blog, please do not hesitate and contact me. I will not disclose your name unless you allow me to do so.

John

john.canessa@gmail.com

Follow me on Twitter: @john_canessa

This site uses Akismet to reduce spam. Learn how your comment data is processed.