ryan.rprimeau
BAN USERI don't claim it's optimized but it will work,
1) I find all substring's in the first word that are the length of the second word.
2) I generate all the permutations for a substring of the first word
3) check every permutation i generate and compare it to the second word
public static void main(String[] args) throws Exception
{
String one = "abcdefg";
String two = "ba";
System.out.println(findifsubperumuation(one, two));
}
//Assumes one is longer than 2
public static boolean findifsubperumuation(String one, String two)
{
int k = two.length();
ArrayList<String> all;
for(int i=0; i<one.length() && i+k<one.length()+1; i++)
{
String current = one.substring(i, i+k);
all=permutation(current);
for(String perm : all)
{
if(perm.equals(two))
{
return true;
}
}
}
return false;
}
public static ArrayList<String> permutation(String s)
{
if(s.length()==1)
{
ArrayList<String> perms = new ArrayList<String>();
perms.add(s);
return perms;
}
ArrayList<String> permsother = permutation(s.substring(1));
ArrayList<String> perms = new ArrayList<String>();
String firstletter = s.substring(0,1);
for(String current : permsother)
{
for(int i=0; i<=current.length(); i++)
{
String Firstpart = current.substring(0,i);
String Secondpart = current.substring(i);
String together = Firstpart.concat(firstletter);
together=together.concat(Secondpart);
perms.add(together);
}
}
return perms;
}
O((n/k)(k)!), it's a horrible solution, but I already had the code for permutation. A better solution would be to look for every substring of size k in the longer string, and check that the number of occurrences of every letter is in this substring is same as the number of every occurrences of every letter in the smaller string.
- ryan.rprimeau March 05, 2013