[HackerRank] Two Strings

Problem

Given two strings, determine if they share a common substring. A substring may be as small as one character.

Example

s1 = 'and'
s2 = 'art'
These share the common substring a.
s1 = 'be'
s2 = 'cat'
These do not share a substring.

Function Description

Complete the function twoStrings in the editor below.

twoStrings has the following parameter(s):

• string s1: a string
• string s2: another string

Returns

• string: either YES or NO

Input Format

The first line contains a single integer p, the number of test cases.

The following p pairs of lines are as follows:

• The first line contains string s1.
• The second line contains string s2.

Constraints

• s1 and s2 consist of characters in the range ascii[a-z].
• 1 <= p <= 10
• 1 <= |s1|, |s2| <= 10^5

Output Format

For each pair of strings, return YES or NO.

Sample Input

2
hello
world
hi
world

Sample Output

YES
NO

Explanation

We have p = 2 pairs to check:

1. s1 = "hello", s2="world". The substrings o and l are common to both strings.
2. a = "hi", b = "world". s1 and s2 share no common substrings.

---

코드

Hash 사용

static String twoStrings(String s1, String s2) {
    HashMap<String, Integer> hm = new HashMap<>();
    String[] s1Array = s1.split("");
    String[] s2Array = s2.split("");

    for (String s : s1Array)
        hm.put(s, 0);

    for (String s : s2Array)
        if (hm.containsKey(s))
            return "YES";

    return "NO";
}

Set 사용

static String twoStrings(String s1, String s2) {
    Set<String> set = new HashSet<>();
    String[] s1Array = s1.split("");
    String[] s2Array = s2.split("");

    for (String s : s1Array)
        set.add(s);

    for (String s : s2Array)
        if (set.contains(s))
            return "YES";

    return "NO";
}

풀이 방법

두 문자열을 한 문자씩 배열에 넣고, 처음 입력받은 단어는 해시맵에 넣는다.
두 번째 단어를 이루는 문자 중 겹치는 것이 있는지 확인한다.

문제를 풀면서 분명 이 코드가 맞는데 hackerrank 사이트에서는 계속 실패로 나왔었다. 자세히 보니 Java7으로 되어있었다. 그래서 java8로 바꿨더니 성공했다.

java7에서 java8 이상으로 바뀌면서 해시 퍼포먼스 향상을 위해 linked list에서 balanced tree로 바뀌었다는데 이 때문인지는 모르겠다. 내가 뭔가 틀렸을지도...😥