Why this method in leetcode is wrong but in my computer is good?


  • 0
    K
    int *f;
    bool wordBreak(string s, unordered_set<string> &dict) {
        int n = s.size();
        f = new int[n];
        return dfs(s, 0, n, dict);
    }
    
    bool dfs(string s, int index, int n, unordered_set<string> &dict){
        if(index==n || f[index]==1)
            return true;
        if(f[index] == 2)
            return false;
        
        for(int i=index+1; i<=n; i++){
            string sub=s.substr(index, i-index);  // [index, i-1]   [i, n]
            if(dict.find(sub)!=dict.end() && dfs(s, i, n, dict)){
                f[index] = 1;
                return true;
            }
        }
        f[index] =2;
        return false;
    }
    

    The test:

    Input: "aaaaaaa", ["aaaa","aa"]
    Output: true
    Expected: false

    In my computer, it's false as expected.
    I believe it's sth about compiler, because I translated it into java, the Java version can pass everything.

    int[] f;
    public boolean wordBreak(String s, Set<String> dict) {
        int n = s.length();
        f = new int[n]; //1 stands for true, 2 stands for false;
        return dfs(s, 0, n, dict);
    }
    
    private boolean dfs(String s, int index, int n, Set<String> dict) {
        if (index == n || f[index] == 1) return true;
        if (f[index] == 2) return false; 
        
        for (int i = index + 1; i <= n; i ++) {
            String sub = s.substring(index, i);
            if (dict.contains(sub) && dfs(s, i, n, dict)) {
                f[index] = 1;
                return true;
            }
        }
        
        f[index] = 2;
        return false;
    }
    

    Can someone give me a hint?


  • 1

    The problem lies in this line of code:

    f = new int[n];
    

    When C++ allocates an array on the heap, it does not initialize the array so it contains random values in it.

    The Java program works because it automatically set all elements in the array to its default value (for int this is 0) when being allocated.

    I added this line and your C++ code got accepted:

    for (int i = 0; i < n; i++) f[i] = 0;

  • 0
    K

    Thanks!

    Initialization is always one of the most important issues.


Log in to reply
 

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