Pure algorithm solution, 36ms BFS.


  • 1
    F

    The straightforward BFS/DFS with state using both x and y will fail because of TLE or memory limit. The key is that we need different way to record state. Instead of using both[x][y], we actually need only one dimension array [w < max(x,y)]. In terms of algorithm design, this is a good example of how to reduce state space. It's pity that similar DFS solution gets 'run time error' due to the fairly small system stack limit.

    bool canMeasureWaterbfs(int x, int y, int z) {
       if(z > x+y || z < 0) return false; 
       if(z == 0) return true;
       if(x < y) return canMeasureWaterbfs(y, x, z);
       //assert x >= y
       vector<char> visited(x+1, 0);
       //bfs
       queue<int> bfsQ;
       bfsQ.push(x);
       visited[x] = 1;
       while(!bfsQ.empty()) {
           int w = bfsQ.front();
           bfsQ.pop();
           if(w == z || w + y == z) return true;
           if( w <= y) {
               //water in Y
               if(w + x == z) return true;
               if(!visited[x - (y - w)]) { 
                   bfsQ.push(x - (y - w));
                   visited[x - (y - w)] = 1;
               }
           }
           //water in X
           int diffX = x - w;
           if(diffX >= y) {
               if(!visited[w + y]) { 
                   bfsQ.push(w+y);
                   visited[w + y] = 1;
               }
           }else {
               if(!visited[y - diffX]) {
                   bfsQ.push(y - diffX);
                   visited[y - diffX] = 1;
               }
           }
    
       }
       return false;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.