NathanLRF
BAN USERI think the initial input should be limited to 0~9. They generate the next number in a way that first count the appearance of continuous same digit and put the count before that digit. Quite similar to compressing string.
public static void LookAndSay(int input){
String str= String.valueOf(input);
System.out.println(str);
if(str.length() == 10){
return;
}
else{
String result = "";
int cnt = 1;
char cur = str.charAt(0);
for(int i=1; i<str.length(); i++){
if(str.charAt(i) == cur)
cnt++;
else{
result = result + String.valueOf(cnt) + cur;
cur = str.charAt(i);
cnt = 1;
}
}
result = result + String.valueOf(cnt) + cur;
LookAndSay(Integer.parseInt(result));
}
}
I believe yes. The char is essentially the same as numbers. So the task is to output the number abcd that a<b<c<d. Here first we use their ascii order(but regardless of uppercase/lowercase) to sort the char sequences to get a candidate pool with size L. Second we generate the sequence with length from L to 1, in a way that we select a char from the candidate pool, the append a smaller one on the front.
The termination condition is when size of our sequence meet the desired length or there is no candidate to choose from the pool.
In this way we don't need to get all the permutation of the chars.
class Coordinate{
private int row;
private int col;
}
ArrayList<Integer> findWord(char[][] grid, int N, String word){
ArrayList<Integer> index = new ArrayList<Integer>();
for(int r = 0; r < N-1; r++){
for(int c = 0; c<N-1; c++){
if(word.charAt(0) == grid[r][c]){
index = searchWord(grid, r, c, N, word);
if(index != null)
break;
}
}
}
return index;
}
Coordinate searchWord(char[][] grid, int r, int c, int N, String word){
//search vertically
if(r + word.length()-1 < N-1){
ArrayList<Coordinate> index = new ArrayList<Coordinate>();
for(int i=0, i<word.length();i++, r++){
if(word.charAt(i) != grid[r][c])
break;
index.add(new Coordinate(r,c));
}
if(index.size() == word.length())
return index;
}
//search horizontally
if(c + word.length()-1 < N-1){
ArrayList<Coordinate> index = new ArrayList<Coordinate>();
for(int i=0, i<word.length();i++, c++){
if(word.charAt(i) != grid[r][c])
break;
index.add(new Coordinate(r,c));
}
if(index.size() == word.length())
return index;
}
//search diagonally
if(r + word.length()-1 < N-1 && c + word.length()-1 < N-1){
ArrayList<Coordinate> index = new ArrayList<Coordinate>();
for(int i=0, i<word.length();i++, c++, r++){
if(word.charAt(i) != grid[r][c])
break;
index.add(new Coordinate(r,c));
}
if(index.size() == word.length())
return index;
}
return null;
}
This one's time complexity is better than simply traversing all the numbers.
- NathanLRF January 05, 2015