Finding the shortest substring containing keywords

Problem: Write a function that takes a String document and a String[] keywords and returns the smallest substring of document that contains all of the strings in keywords.


Notes:

• document will contain at least 1 word

• document will separate words by a single space

• A word can only contain [a-z] and can appear multiple times in the document

• keywords will be a distinct list of words

• Matches must be perfect (ie bat and batman do not match)

• If there are multiple shortest substrings, pick the first one

• keywords can appear in the substring in any order

• The substring length is counted in words, not characters

• Must be written in Java 7 and provide a class called Solution with a method solution

Examples


Input:

document: "a b c d a"
keywords: ["a", "c", "d"]

Output: "c d a"


Input:

document: "world there hello hello where world"
keywords: ["hello", "world"]

Output: "world there hello"

My attempt:

```
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

//Time Complexity: O(w + ws)
//Space Complexity: O(s)
//Where w is the number of words in the document, and s is the number of search terms
public class Solution {
private Map snippetDataPoints = new HashMap();
private String[] words, searchTerms;
private int shortestSnippetStart = 0, shortestSnippetEnd, currentSnippetStart = 0;

public static String solution(String document, String[] searchTerms) {
Solution solution = new Solution (document.split(" "), searchTerms);//document.split isnt the most efficient, but we are already over O(n), and this keeps it simple
return solution.solve();
}

private Solution(String[] words, String[] searchTerms){
this.words = words;
this.searchTerms = searchTerms;
shortestSnippetEnd=words.length;
}

private String solve(){
for(int i=0;i currentPositionEnd - c

Problems / Bugs

-
The following calls will all throw an ArrayIndexOutOfBoundsException

String document = "a b c d";
System.out.println(Solution.solution(document, new String[]{"g"}));
System.out.println(Solution.solution(document, new String[]{"g", "a", "s", "s"}));
System.out.println(Solution.solution(document, new String[]{"a", "b" ,"c", "d"}));

because of

for (int i = shortestSnippetStart; i <= shortestSnippetEnd; i++) {

Assuming you have fixed the above by changing to

for (int i = shortestSnippetStart; i < shortestSnippetEnd; i++) {

The above calls will return


a b c d

a b c d

a b c

-
The following will throw an exception if snippet.length==0

snippet.deleteCharAt(snippet.length()-1);

General

-
you shouldn't do string concatenation inside StringBuilder.append() method. The append() method returns a StringBuilderso you should just stack the calls like

snippet.append(words[i])
       .append(" ");

-
you shouldn't declare multiple variables in a single line, because this removes readability of the code.

-
give your conditions/variables the possibility to breathe

for(int i = shortestSnippetStart; i<=shortestSnippetEnd; i++){

should be

for(int i = shortestSnippetStart; i <= shortestSnippetEnd; i++) {

StackExchange Code Review Q#77473, answer score: 2