Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Challenge:

Given two strings, A and B. Find if there is a substring that appears in both A and B.

Specifications:

Several test cases will be given to you in a single file. The first line of the input will contain a single integer T, the number of test cases.

Then there will be T descriptions of the test cases. Each description contains two lines. The first line contains the string A and the second line contains the string B.

For each test case, display YES (in a newline), if there is a common substring.
Otherwise, display NO.

Implementation:

import java.util.Scanner;
import java.util.Set;
import java.util.HashSet;

public class TwoStrings {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        for (int i = Integer.parseInt(input.nextLine()); i> 0; i--) {
            String sub1 = toDiscreteString(input.nextLine());
            String sub2 = toDiscreteString(input.nextLine());
            boolean success;
            if (sub1.length() < sub2.length()) {
                success = hasCommonSubString(sub1, sub2);
            } else {
                success = hasCommonSubString(sub2, sub1);
            }
            System.out.println(success ? "YES" : "NO");
        }
    }

    private static boolean hasCommonSubString(String shorter, String longer) {
        for (int i = 0; i < shorter.length(); i++) {
            if (longer.indexOf(shorter.charAt(i)) > -1) {
                return true;
            }
        }
        return false;
    }

    private static String toDiscreteString(String input) {
        Set<Character> set = new HashSet<>();
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < input.length(); i++) {
            if (set.add(input.charAt(i))) {
                result.append(input.charAt(i));
            }
        }
        return result.toString();
    }
}

This is a challenge found on HackerRank and passes all test cases. Is there a more efficient method? Is this overly-convoluted? Java 8 is available.

share|improve this question

I am guessing indexOf is O(n). A faster way may be to add all the characters of a string to a set. Then call contains for each character of the second string (I would imagine that contains is on average O(1) for a hash set or O(lg(n)) for a tree set.)

private static boolean hasCommonSubString(String shorter, String longer)  
{

    Set<Integer> set = shorter.chars()
                              .boxed()
                              .collect(Collectors.toSet());

    return longer.chars().anyMatch(set::contains);    
} 
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.