Skip to content

Instantly share code, notes, and snippets.

@MaksimDmitriev
Last active October 22, 2016 15:58
Show Gist options
  • Save MaksimDmitriev/e129bff5f65c52518f033732a6c33a88 to your computer and use it in GitHub Desktop.
Save MaksimDmitriev/e129bff5f65c52518f033732a6c33a88 to your computer and use it in GitHub Desktop.
Find all permutations of source within input
public class Main {
public static void main(String[] args) {
System.out.println(getPermutations("bbca", "abbca"));
}
private static Set<String> getPermutations(String source, String input) {
if (source == null || input == null || source.isEmpty() || input.isEmpty()) {
return null;
}
if (source.length() > input.length()) {
throw new IllegalArgumentException();
}
Set<String> result = new HashSet<>();
Map<Character, Integer> sourceMap = new HashMap<>();
for (int i = 0; i < source.length(); i++) {
char currentChar = source.charAt(i);
if (sourceMap.containsKey(currentChar)) {
sourceMap.put(currentChar, sourceMap.get(currentChar) + 1);
} else {
sourceMap.put(currentChar, 1);
}
}
Map<Character, Integer> buffer = new HashMap<>();
for (int i = 0; i <= input.length() - source.length(); i++) {
int jEnd = i + source.length();
for (int j = i; j < jEnd; j++) {
char currentChar = input.charAt(j);
if (buffer.containsKey(currentChar)) {
buffer.put(currentChar, buffer.get(currentChar) + 1);
} else {
buffer.put(currentChar, 1);
}
}
if (buffer.equals(sourceMap)) {
result.add(input.substring(i, jEnd));
}
buffer.clear();
}
return result;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment