Software Programming

Kunuk Nykjaer

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

with one comment


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 c1 * p1 + c2 * p2 + … + cn * pn
where ci is a unique value for the current char in the string and where pi is a unique prime number value for the ci 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

Reference:
http://stackoverflow.com/questions/10727118/how-to-find-all-permutations-of-a-given-word-in-a-given-text

Advertisements

Written by kunuk Nykjaer

May 25, 2012 at 1:20 pm

Posted in Algorithm, Java

Tagged with

One Response

Subscribe to comments with RSS.

  1. 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/

    Cassie

    October 30, 2012 at 11:20 am


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: