educative.io

Java solution using matched variable and shallow copy

Courses
,
#1

Hi, I managed to solve the problem using the matched variable as it was taught in the previous lessons. Here is my code for this example using the matched variable and a shallow copy

May not be optimal, but went off the same intuition that was in previous lessons.

import java.util.*;

class WordConcatenation {
  public static List<Integer> findWordConcatenation(String str, String[] words) {
    List<Integer> resultIndices = new ArrayList<Integer>();
    int wordCount = words.length;
    int wordLength = words[0].length();
    Map<String, Integer> wordsMap = new HashMap<>();
    for (String word : words) {
      wordsMap.put(word, wordsMap.getOrDefault(word, 0) + 1);
    }
    for (int i = 0; i <= str.length() - wordCount * wordLength; i++) {
      int matched = 0;
      // shallow copy the map
      Map<String, Integer> tempMap = new HashMap<>(wordsMap);
      for (int j = 1; j <= wordCount; j++) {
    
        String word = str.substring(i + (j * wordLength - wordLength), i + (j * wordLength));

        // if not in map, break
        if (!tempMap.containsKey(word)) break;

        // if in map and its already 0 break.
        if (tempMap.get(word) == 0) break;

        // add to matched
        tempMap.put(word, tempMap.get(word) - 1);
        if (tempMap.get(word) == 0) matched++;

        // if matched == tempmap.size add to result indices (i)
        if (matched == tempMap.size()) {
          resultIndices.add(i);
        }
      }
    }
    return resultIndices;
  }
}