## Interview-question: How to find all permutations of a given word in a given text? – Java example

Write a function (in Java) to find all permutations of a given word that appear in a given text. For example, for word abc and text abcxyaxbcayxycab the function should return abc, bca, cab.

**Answer:**

To find a permutation of a string you can use number theory.

There is a method where you can calculate a hash of a string using prime numbers. Every permutation of the same string will give the same hash value. All other string combination which is not a permutation will give some other hash value.

The hash-value is calculated by c_{1} * p_{1} + c_{2} * p_{2} + … + c_{n} * p_{n}

where c_{i} is a unique value for the current char in the string and where p_{i} is a unique prime number value for the c_{i} char.

Here is the implementation.

Main.java

// Author: Kunuk Nykjaer public class Main { final static int[] primes = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113 }; public static void main(String[] args) { final char[] text = "abcxaaabbbccyaxbcayaaaxycab" .toCharArray(); int hash = val(new char[]{'a','b','c'}); for (int i = 0; i < text.length - 2; i++) { char[] _123 = new char[]{text[i],text[i+1],text[i+2]}; if(val(_123)==hash){ System.out.println(new String(_123) ); } } } static int p(char c) { return primes[(int)c - (int)'a']; } static int val(char[] cs) { return p(cs[0])*(int)cs[0] + p(cs[1])*(int)cs[1] + p(cs[2])*(int)cs[2]; } }

The output is: abc bca cab

Great post!

This page was a big help as well since it explains it in detail:

http://www.programmerinterview.com/index.php/recursion/permutations-of-a-string/

CassieOctober 30, 2012 at 11:20 am