Just could not pass "interaction"


  • 0
    A
    public class Solution {
        public List<String> generateAbbreviations(String word) {
            List<String> list = new ArrayList<>();
            generateAbbreviations(list, word, 0);
            return list;
        }
        
        public void generateAbbreviations(List<String> list, String s, int n) {
            list.add(s);
            if (n < s.length()) {
                for (int i = 1; i <= s.length() - n; i++) 
                    for (int j = n; j <= s.length() - i; j++) 
                        generateAbbreviations(list, s.substring(0, j) + i + s.substring(j + i), j + 2);
            } else return;
        }
    }
    

    I thought my backtracking solution is correct after checking several simple testcases, while it could not pass the testcase "interaction". Has anyone met with this problem as well? Or is there something wrong with my solution?


  • 0
    A

    I've found the problem

    public List<String> generateAbbreviations(String word) {
        List<String> list = new ArrayList<>();
        generateAbbreviations(list, word, 0);
        return list;
    }
    
    public void generateAbbreviations(List<String> list, String s, int n) {
        list.add(s);
        if (n < s.length()) {
            for (int i = 1; i <= s.length() - n; i++) 
                for (int j = n; j <= s.length() - i; j++) {
                	int cnt = 0, in = i;
                	while (in > 0) {in /= 10; cnt++;}
                    generateAbbreviations(list, s.substring(0, j) + i + s.substring(j + i), j + 1 + cnt);
                }
        } else return;
    }

Log in to reply
 

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