4ms easy and clean Java two pointer DFS solution


  • 0

    Create an array to store every char of the result string. Use two pointer start and end to mark the index of the array which ready to edit, then use dfs to compute every possible combination.

    
        public List<String> findStrobogrammatic(int n) {
            char[] strob = new char[] {'0','1','2','3','4','5','9','7','8','6'};
            char[] digits = new char[] {'0', '1', '6', '8', '9'};
            char[] retStr = new char[n];
            List<String> ret = new ArrayList<>();
            DFS(ret, retStr, 0, n - 1, digits, strob);
            return ret;
        }
        
        private void DFS(List<String> ret, char[] retStr, int start, int end, char[] digits, char[] strob){
            if(start > end){
                ret.add(new String(retStr));
                return;
            }
            for(int i = 0; i < digits.length; i++){
                if(start != end && start == 0 && i == 0) continue;
                if(start == end && (i == 2 || i == 4)) continue;
                retStr[start] = digits[i];
                retStr[end] = strob[digits[i] - '0'];
                DFS(ret, retStr, start + 1, end - 1, digits, strob);
            }
        }
    

Log in to reply
 

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