shane030716
BAN USERWe need to handle the situation where one word starts with another word.
For example,
input
herewego
Since "he" is a valid word, we don't want the program to fail after finding "he".
The output should be "here we go"
public static String construct(String s) {
if (s == null || s.isEmpty()) return null;
List<String> result = construct(s, 0, 1);
return StringUtils.join(result, " ");
}
public static List<String> construct(String s, int start, int end) {
if (s == null || s.isEmpty()) return null;
if (start > end) return null;
if (end > s.length()) {
if (end - start == 1) {
return new ArrayList<String>();
} else {
return null;
}
}
String substring = s.substring(start, end);
if (isAWord(substring)) {
List<String> rest = construct(s, end, end + 1);
if (rest != null) {
rest.add(0, substring);
return rest;
}
}
return construct(s, start, end + 1);
}
public static boolean isAWord(String s) {
// check if it's a valid word
}
int rand3() {
int random = 2 * rand2() + rand2();
if (random < 3) return random;
return rand3();
}
Convert all in the input into an undirected graph.
Then the problem basically becomes finding the number of direct neighbours and the number of indirect neighbours of a given node.
- shane030716 August 29, 2016Perform a breath-first-search from the given node, you need to add a variable to keep track of the current depth. If the current depth is 1 and you found a new node, increment the number of direct neighbours, if it's larger than 1, increment the number of indirect neighbours.