Algorithms/RearrangeWord.java at master · manjeersrujan/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;

public class RearrangeWord {
	/*
	 * Complete the 'rearrangeWord' function below.
	 *
	 * The function is expected to return a STRING. The function accepts STRING word
	 * as parameter.
	 */

	public static void main(String[] args) {

		System.out.println(new RearrangeWord().getPerms("abcd", new HashSet<String>(), ""));
	}

	public static String rearrangeWord(String word) {

		// Write your code here
		if (word == null || word.length() <= 1) {
			return "no answer";
		}

		Set<String> perms = new LinkedHashSet<String>();
		perms = getPerms(word, perms, "");

		List<String> pList = new ArrayList<>(perms);
		Collections.sort(pList);
		int indexOf = pList.indexOf(word);

		if (indexOf <= pList.size() - 2) {
			return pList.get(indexOf + 1);
		} else {
			return "no answer";
		}

	}

	public static Set<String> getPerms(String str, Set<String> perms, String preF) {

		if (str.length() == 1) {
			if (preF != null) {
				perms.add(preF + str);
			} else {
				perms.add(str);
			}
			return perms;
		}

		if (str.length() == 2) {
			if (preF != null) {
				perms.add(preF + str.charAt(1) + str.charAt(0));
				perms.add(preF + str);
			} else {
				perms.add("" + str.charAt(1) + str.charAt(0));
				perms.add(str);
			}

			return perms;
		}

		for (int i = 0; i < str.length(); i++) {
			char c = str.charAt(i);
			Set<String> perms2 = null;
			if (i == 0) {
				perms2 = getPerms(str.substring(i + 1, str.length()), perms, "" + (preF+c));
			} else if (i == str.length() - 1) {
				perms2 = getPerms(str.substring(0, i), perms, "" + (preF+c));
			} else {
				perms2 = getPerms(str.substring(0, i) + str.substring(i + 1, str.length()), perms, "" + (preF+c));
			}
			for (String nStr : perms2) {
				if(preF != null) {
					perms.add(preF +c + nStr);
				}
			}
		}
		return perms;
	}

	class MyComparator implements Comparator<Integer> {

		@Override
		public int compare(Integer o1, Integer o2) {

			if (o1 == o2 || o1.equals(o2)) {
				return 0;
			}

			int o1C = Integer.bitCount(o1);
			int o2C = Integer.bitCount(o2);

			if (o1C != o2C) {
				return o1C - o2C;
			} else {
				return o1 - o2;
			}
		}
	}

	public static List<Integer> rearrange(List<Integer> elements) {
		Collections.sort(elements, new Comparator<Integer>() {

			@Override
			public int compare(Integer o1, Integer o2) {

				if (o1 == o2 || o1.equals(o2)) {
					return 0;
				}

				int o1C = Integer.bitCount(o1);
				int o2C = Integer.bitCount(o2);

				if (o1C != o2C) {
					return o1C - o2C;
				} else {
					return o1 - o2;
				}
			}
		});
		return elements;
	}

}