Unique25

mail@pastecode.io avatar
unknown
java
a month ago
1.9 kB
3
Indexable
Never
package random;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Unique25 {

    private static Map<String, Boolean> provided;

    private static boolean findUnique25(int i, int mask, String curWord, boolean[][] memo){


        if(i > 0 && i%5 == 0){
            //System.out.println(curWord + " " + i);
            if(provided.containsKey(curWord)){
                System.out.println(curWord + " " + i);
                provided.put(curWord, true);
                if(i == 25)
                    return true;
            }else
                return false;

            //curWord="";
        }


        if(memo[i][mask])
            return false;


        for(int k=0; k<26; k++){
            if((mask & (1 << k)) == 0){
                if(findUnique25(i+1, mask|(1<<k), i%5 == 0 ? ""+(char)('a' + k): curWord+(char)('a' + k), memo)){
                    return true;
                }
            }
        }

        if(i%5 == 0){
            System.out.println("Removed " + curWord );
            provided.put(curWord, false);
        }

        memo[i][mask] = true;


        return false;

    }
    public static void main(String[] args) {

        //String[] words=  {"abcde", "fghij", "klmno", "pqrst", "uvwxy", "zabcd", "apple", "zebra", "ocean", "quick", "world", "jumps", "foxes", "liver"};
        //String[] words=  {"abcde", "fghij", "fghij", "fghij", "fghij", "fghij", "fghij"};
        String[] words=  {"abcde", "fghij", "fklmn", "gopqr", "hstuv", "iwxyz"};

        provided = new HashMap();
        for(String word: words)
            provided.put(word, false);

        boolean[][] memo = new boolean[25][(1 << 26)-1];

        findUnique25(0, 0, "", memo);


        for(Map.Entry<String, Boolean> e: provided.entrySet())
            if(e.getValue())
                System.out.println(e.getKey());

    }



}
Leave a Comment