corbindlee
BAN USERflatten (Node head) {
if (head == null) return;
print(head.a);
Node n = head;
while (n.down != null) {
n = n.down;
print(n.a);
}
flatten(head.right);
}
Assuming the character array given is a set (no duplicates)
public class MinLengthWord {
public static void main(String args[]) {
String[] dic = { "addds", "asdfoisfiodijf" };
char[] c = { 'a', 's', 's' };
System.out.print(minLengthWord(c, dic));
}
public static String minLengthWord(char[] chars, String[] dic) {
int min = Integer.MAX_VALUE;
int minIndex = -1;
for (int i = 0; i < dic.length; i++) {
// Check if current word (dic[i]) is big enough to contain all characters and smaller than
// current smallest word
if (dic[i].length() >= chars.length && (dic[i].length() < min || min == Integer.MAX_VALUE)) {
// Check if current word contains all characters in chars
if (containsAll(dic[i], chars)) {
min = dic[i].length();
minIndex = i;
}
}
}
if (minIndex == -1) {
System.out.println("No words found that contain all characters.");
return null;
} else {
return dic[minIndex];
}
}
public static boolean containsAll(String s, char[] chars) {
boolean[] c = new boolean[256];
for (int j = 0; j < s.length(); j++) {
c[(int) s.charAt(j)] = true;
}
for (int j = 0; j < chars.length; j++) {
if (!c[(int) chars[j]]) {
return false;
}
}
return true;
}
Code is a bit clunky, but it can solve the above mentioned input of aaa ... ab without a problem.
public static void printSubStrings(String s) {
int numLetters = 26; // Letters in the alphabet
// Create an ArrayList containing 26 ArrayLists that store the index (in s) for each character in s,
// indexes of 'a' are stored in 1st ArrayList ... indexes of 'z' are stored in 26th ArrayList
List<List<Integer>> list1 = new ArrayList<List<Integer>>(numLetters);
List<List<Integer>> list2 = new ArrayList<List<Integer>>(numLetters);
// Construct 2 ArrayLists since findFirst() and findLast() will change them
for (int i = 0; i < numLetters; i++) {
list1.add(i, new ArrayList<Integer>());
list2.add(i, new ArrayList<Integer>());
}
// Find index of first vowel
int start = -1;
for (int i = 0; i < s.length(); i++) {
if (isVowel(s.charAt(i))) {
start = i;
break;
}
}
if (start == -1) {
System.out.println("ERROR: Invalid String, no vowels");
return;
}
// Find index of last consonant
int end = -1;
for (int i = s.length()-1; i >= 0; i--) {
if (!isVowel(s.charAt(i))) {
end = i;
break;
}
}
if (end == -1) {
System.out.println("ERROR: Invalid String, no consonants");
return;
}
// Check if a substring starting with a vowel and ending in a consonant exists
if (start > end) {
System.out.println("ERROR: Invalid String, no valid substrings");
return;
}
// Load String data into list
for (int i = start; i <= end; i++) {
list1.get(indexOf(s.charAt(i))).add(i);
list2.get(indexOf(s.charAt(i))).add(i);
}
System.out.println(findFirst(s, list1, end));
System.out.println(findLast(s, list2, end));
}
public static String findFirst(String s, List<List<Integer>> list, int end) {
int a = indexOf('a');
int e = indexOf('e');
int i = indexOf('i');
int o = indexOf('o');
int u = indexOf('u');
int firstV; // Index of alphabetical first vowel
int last = end; // Index of last letter in the substring
// Find firstV
if (!list.get(a).isEmpty()) { firstV = a; }
else if (!list.get(e).isEmpty()) { firstV = e; }
else if (!list.get(i).isEmpty()) { firstV = i; }
else if (!list.get(o).isEmpty()) { firstV = o; }
else { firstV = u; }
// Go through 2nd characters in substring to find alphabetical first, deleting the rest
// If multiple substrings have same 2nd character, repeat with 3rd, 4th, etc. until 1 substring left
for (int j = 1; list.get(firstV).size() > 1; j++) { // j = number of characters after firstV we are comparing
int smallest = (int) s.charAt(list.get(firstV).get(0) + j); // int value of smallest character found so far
for (int m = 0; m < list.get(firstV).size(); m++) { // iterate through all substrings that start with firstV
// If the last character looked at was a consonant, this is the smallest substring
if (!isVowel(s.charAt(list.get(firstV).get(m) + (j-1)))) {
list.get(firstV).set(0, list.get(firstV).get(m));
list.get(firstV).subList(1, list.get(firstV).size()).clear();
break;
}
char current = s.charAt(list.get(firstV).get(m) + j);
// Check if this char is the smallest one so far
// If so, delete all already checked substrings as they are worse than this one
if ((int) current < smallest) {
smallest = (int) current;
list.get(firstV).subList(0, m).clear();
m = 0;
}
// Delete any alphabetically later ones as they are worse than the smallest
else if ((int) current > smallest) {
list.get(firstV).remove(m);
m--;
}
}
}
// Find the first consonant after the starting vowel and that will be the end of the substring
for (int j = list.get(firstV).get(0); j <= end; j++) {
if (!isVowel(s.charAt(j))) {
last = j;
break;
}
}
return s.substring(list.get(firstV).get(0), last + 1);
}
public static String findLast(String s, List<List<Integer>> list, int end) {
int a = indexOf('a');
int e = indexOf('e');
int i = indexOf('i');
int o = indexOf('o');
int u = indexOf('u');
int lastV; // index of alphabetical last vowel
// Find lastV
if (!list.get(u).isEmpty()) { lastV = u; }
else if (!list.get(o).isEmpty()) { lastV = o; }
else if (!list.get(i).isEmpty()) { lastV = i; }
else if (!list.get(e).isEmpty()) { lastV = e; }
else { lastV = a; }
// Go through 2nd characters in substring to find alphabetical last, deleting the rest
// If multiple substrings have same 2nd character, repeat with 3rd, 4th, etc. until 1 substring left
for (int j = 1; list.get(lastV).size() > 1; j++) {
int largest = (int) s.charAt(list.get(lastV).get(0) + j); // int value of largest character found so far
for (int m = 0; m < list.get(lastV).size(); m++) {
// Make sure we don't go past the last consonant
if (list.get(lastV).get(m) + j > end) {
list.get(lastV).remove(m);
m--;
continue;
}
char current = s.charAt(list.get(lastV).get(m) + j);
// Check if this char is the alphabetical latest one so far
// If so, delete all already checked substrings as they are worse than this one
if ((int) current > largest) {
largest = (int) current;
list.get(lastV).subList(0, m).clear();
m = 0;
}
// Delete any alphabetical earlier ones as they are worse than the previous
else if ((int) current < largest) {
list.get(lastV).remove(m);
m--;
}
}
}
// Return String from that vowel to the last consonant
return s.substring(list.get(lastV).get(0), end + 1);
}
public static boolean isVowel(char c) {
return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');
}
public static int indexOf(char c) {
return (int) c - 97;
}
Reprothymellen, Consultant at Accolite software
I am a Correctional officer . I have the primary role of maintaining order within a detention facility. My hobby is ...
Repdubinalinda4, Animator at Apache Design
Hello, I am a school librarian from Lewistown USA. I work in public or private schools at elementary, middle and ...
RepEshikaLopez, general assistant at MMSS
Dedicated and reliable general assistant with background in and strong knowledge of secretarial and administrative principles. Capable of providing direct ...
- corbindlee July 19, 2016