kira
BAN USERyy made a good point. All are perfect except one fault I think. When A.Miss: 1.(2) missed set isn't empty, we should further check if the current char in correct is equal to the missing char. if yes, we continue; o/w we return false.
In fact, the missing set should only contain one char.
Ideas from the sheldon's, modified for holding multiple snakes exist in the same time. I think there is no bug here, just for reference.
//2,loop the matrix for filling
public int filldp(int[][] grid,int[][] dp){
if(grid.length==0 || grid[0].length==0) throw new IllegalArgumentException("");
int rows = grid.length, cols = grid[0].length;
//int[][] dp = new int[rows][cols];
int max = 0;
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
if(dp[i][j]==0){
max = Math.max(max,fill(grid,i,j,dp));
}else{
max = Math.max(max, dp[i][j]);
}
}
}
return max;
}
//1,fill the dp matrix
public int fill(int[][] grid, int r, int c,int[][] dp){
if(r<0 || c<0 || r>grid.length-1 || c>grid[0].length-1){
return 0;
}
if(dp[r][c]!=0){
return dp[r][c];
}
int left=0,right=0,down=0,up=0;
if(r-1>=0 && grid[r-1][c]==grid[r][c]+1){
up = fill(grid,r-1,c,dp);
}
if(r+1<grid.length && grid[r+1][c] == grid[r][c]+1){
down = fill(grid,r+1,c,dp);
}
if(c-1>=0 && grid[r][c-1] == grid[r][c]+1){
left = fill(grid,r,c-1,dp);
}
if(c+1<grid.length && grid[r][c+1] == grid[r][c]+1){
right = fill(grid,r,c+1,dp);
}
dp[r][c] = Math.max(Math.max(up, down),Math.max(left, right))+1;
return dp[r][c];
}
//4, DFS for finding snake paths
public void findall(int[][] grid,int[][] dp, ArrayList<ArrayList<Integer>> paths, ArrayList<Integer> one, int r, int c){
if(dp[r][c]==1){
one.add(grid[r][c]);
paths.add(one);
System.out.println(one);
return;
}
one.add(grid[r][c]);
if(r-1>=0 && dp[r-1][c] == dp[r][c]-1 && grid[r-1][c] == grid[r][c] +1)
findall(grid,dp,paths,new ArrayList<Integer>(one),r-1,c);
if(r+1<grid.length && dp[r+1][c] == dp[r][c]-1 && grid[r+1][c] == grid[r][c] +1)
findall(grid,dp,paths,new ArrayList<Integer>(one),r+1,c);
if(c-1>=0 && dp[r][c-1] == dp[r][c]-1 && grid[r][c-1] == grid[r][c] +1)
findall(grid,dp,paths,new ArrayList<Integer>(one),r,c-1);
if(c+1<grid[0].length && dp[r][c+1] == dp[r][c] -1 && grid[r][c+1] == grid[r][c] +1)
findall(grid,dp,paths,new ArrayList<Integer>(one),r,c+1);
}
//3,main func for finding all the snake seqs
// assume we just need to find the elements along the snake paths not the coordinates
public ArrayList<ArrayList<Integer>> findallsnakes(int[][] grid){
if(grid.length==0 || grid[0].length==0) throw new IllegalArgumentException("");
ArrayList<ArrayList<Integer>> snakes = new ArrayList<ArrayList<Integer>>();
int rows = grid.length, cols = grid[0].length;
int[][] dp = new int[rows][cols];
int max = filldp(grid,dp);
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
if(dp[i][j] == max){
findall(grid,dp,snakes,new ArrayList<Integer>(),i,j);
}
}
}
return snakes;
}
The code does has problem. But it may not be as the tester said. It's true we can't get the input as 1868488 since the '8' is the not working key, however, we may have the expected as 186848 or 186847. Now when actual input is 164,
for 186848 as expected, the result should be right;
for 186847 as expected, the result should be wrong.
But the mindless's code will regard both as wrong.
And the modification is similar to tester's solution. The code is shown as follows.
public boolean checkValid(String actual, String expected){
char faultKey = '\0';
int i = 0, j = 0;
for(;i<actual.length() && j < expected.length();j++){
if(actual.charAt(i)!=expected.charAt(j)){
if(faultKey == '\0'){
faultKey = expected.charAt(j);
}else{
if(faultKey != expected.charAt(i))
return false;
}
i--;
}
i++;
}
while(j<expected.length() && expected.charAt(j) == faultKey)
j++;
return (i==actual.length() && j == expected.length())? true:false;
}
Yeah, it still exists problem. The modification is easy. Just save the num1 in the second for iteration, and use a temp_num1 in the inner while iteration. Since in while{}, the num1 has been changed, but when we're out of the while{} and in the second for{} again, we need recover the num1 to the original one (front 1st for{}). Codes are shown as fellows.
public static boolean check(String num){
for(int i = 1; i<num.length();i++){
int num1 = Integer.parseInt(num.substring(0,i));
for(int j = i+1; j<num.length();j++){
int temp_num1 = num1;
int num2 = Integer.parseInt(num.substring(i,j));
int thirdIndex = j;
int rest = Integer.parseInt(num.substring(thirdIndex,num.length()));
while(temp_num1+num2<=rest){
int num3 = temp_num1+num2;
String newNum = (new Integer(num3)).toString();
int length = newNum.length();
if(thirdIndex+length > num.length()){
break;
}
if(num.substring(thirdIndex,thirdIndex+length).equals(newNum)){
thirdIndex += length;
if(thirdIndex == num.length()){
return true;
}
temp_num1 = num2;
num2= num3;
rest = Integer.parseInt(num.substring(thirdIndex,num.length()));
}else{
break;
}
}
}
}
return false;
}
public boolean colorfulNum(int num) throws Exception{
ArrayList<Integer> numList = new ArrayList<Integer>();
while(num!=0){
numList.add(num%10);
num /= 10;
}
HashSet<Integer> mSet = new HashSet<Integer>(100);
for(int conLen = 1; conLen<=numList.size();conLen++){
for(int start=0;start<=numList.size()-conLen;start++){
int multiple = 1;
for(int next=start;next<conLen+start;next++){
multiple *= numList.get(next);
}
/*if(multiple<0)
throw new Exception("overflow");//overflow*/
if(mSet.contains(multiple)){
return false;
}else{
mSet.add(multiple);
}
}
}
return true;
}
@Park NIce change!
- kira August 13, 2014