Generalized abbreviation


  • 3
    X

    Given an Generalized abbreviation function:
    for example for the word "word"
    f(word) would return: word, 1ord, w1rd, wo1d, wor1, 2rd, w2d, wo2, 1o1d, 1or1, w1r1, 1o2, 2r1, 3d, w3, 4


  • 0
    S
    class Solution {
    private:
    bool isDigit(char c){
    	return (c>='0' && c<='9');
    }
    
    string intToString(int a){
    	string s="";
    	
    	while(a){
    		s+=('0' + a%10);
    		a/=10;
    	}
    	
    	return s;
    }
    
    void solve(string word,set<string>& ans){
    	int n=word.size(),i,j,k,num,d;										
    			
    	if(ans.count(word)==0){
    		ans.insert(word);
    	}else{
    		dup++;
    		return;
    	}				
    	
    	for(i=0;i<n;i++){
    		if(!isDigit(word[i])){
    			string s = "";
    			int num=1;
    			for(j=i-1,d=1;j>=0;j--,d*=10){									
    				if(!isDigit(word[j]))
    					break;
    				num = num + d*(word[j]-'0');
    			}
    			
    			for(k=0;k<=j;k++)
    				s+=word[k];
    			
    			int cur=0;
    			for(j=i+1;j<n;j++){									
    				if(!isDigit(word[j]))
    					break;
    				cur = cur*10 + word[j]-'0';
    			}
    			
    			s+=intToString(cur+num);
    			
    			for(k=j;k<n;k++)
    				s+=word[k];
    				
    			solve(s,ans);
    		}
    	}
    	
    }
    
    public:	
    set<string> f(string word){
    	set<string> ans;	
    	solve(word,ans);
    	return ans;
    }
    };

  • 2

    This is my solution, suppose we don't allow results like "11rd" or "12d" which has two digits adhere together (as I don't see them from the question), anyway, the solution is probably not the best one, but it works. For input string "word", it outputs:
    [wor1, 2rd, 1o1d, 1ord, w2d, 1or1, w1r1, 2r1, 3d, 1o2, 4, w1rd, wo2, wo1d, w3, word], for input string "wor", it outputs [2r, 1o1, 3, 1or, wo1, w1r, wor, w2], and for input string "w", it outputs [1, w].

    Here is the Java code using recursion:

    public Set<String> generate(String word) {
      int n = word.length();
      Set<String> res = new HashSet<>();
      
      for (int i = 0; i < n; i++) {
        for (int len = 0; len <= n - i; len++) {
          String a = word.substring(0, i);
          String b = len > 0 ? String.valueOf(len) : "";
          String c = word.substring(i + len);
          
          res.add(a + b + c);
          
          if (c.length() >= 2) {
            Set<String> rest = generate(c.substring(1));
            
            for (String d : rest)
              res.add(a + b + c.substring(0, 1) + d);
          }
        }
      }
      
      return res;
    }
    

  • 4
    T

    Python recursive solution:

    def abbreviate(s):
        # abbreviate outputs all possible abbreviation of a word:
        # ex: word-> w1rd, wo1d, wor1, 1ord, 1o1d, wo2
        if not s:
            return ['']
        else:
            res = abbreviate(s[:-1])
            return [w + s[-1] for w in res] + [extendWordWith1(w) for w in res]
    
    
    def extendWordWith1(word):
        if word and word[-1].isdigit():
            #if the end of the word is a number, add 1 to that number
            idx = len(word)-1
            while idx-1>=0 and word[idx-1].isdigit():
                idx -=1
            return word[:idx] + str(int(word[idx:]) + 1)
        else:
            return word+'1'

  • 0
    J

    No need of using set, java version.

    public List<String> transfer(String string) {
    	List<String> result = new ArrayList<String>();
    	int length = string.length();
    	helper(result, string, 0, length);
    	result.add(string);
    	return result;
    }
    
    public void helper(List<String> list, String string, int index, int length) {
    	for (int i = index; i < length; i++) {
    		String left = string.substring(0, i);
    		String right = string.substring(i + 1);
    		String t = left + "*" + right;//turn string abc into *bc and all the possibility
    		list.add(handle(t));
    		helper(list, t, i+1, t.length());
    	}
    }
    public String handle(String str){//handle *b* to 1b1.. count the apperance of *
    	int len = 0;
    	StringBuilder sb = new StringBuilder();
    	int start =0;
    	while(start < str.length()){
    		if(str.charAt(start)=='*'){
    			len++;
    			start++;
    		}
    		else{
    			if(len>0){
    				sb.append(len);
    				len=0;
    				sb.append(str.charAt(start++));
    			}
    			else sb.append(str.charAt(start++));
    		}
    	}
    	if(len>0) sb.append(len);
    	return sb.toString();
    }

  • 0
    H

    Here is my solution. I know maybe it's not efficient but here it is. But the final result should be refined too as it outputs the result like this for "word"

    [wor1, 111d, 11rd, 1o1d, 1ord, 11r1, 1o11, 1or1, w111, w1r1, wo11, 1111, w1rd, w11d, wo1d, word]
    

    Here is the code:

    public static Set<String> abbreviation (String word){
        Map<String, HashSet<String>> res = new HashMap<>();
    
        Abb(word, res);
    
        return res.get(word);
    }
    
    
    public static void Abb(String word, Map<String ,HashSet<String>> res){
        if (word.length() == 1){
            if (!res.containsKey(String.valueOf(word.charAt(0)))) {
                HashSet<String> tmpSet = new HashSet<>();
                tmpSet.add(String.valueOf(word.charAt(0)));
                tmpSet.add(String.valueOf(1));
    
                res.put(String.valueOf(word.charAt(0)), tmpSet);
            }
        }
        else {
            Abb(word.substring(1), res);
            Abb(word.substring(0, (word.length() - 1)), res);
            HashSet<String> concatSet = new HashSet<>();
    
            for(String rightStr: res.get(word.substring(1)))
                for(String leftStr: res.get(word.substring(0, word.length() - 1)))
                    if (leftStr.substring(1, leftStr.length()).equals(rightStr.substring(0, rightStr.length() - 1)))
                        concatSet.add(leftStr.concat(String.valueOf(rightStr.charAt(rightStr.length() - 1))));
    
            res.put(word, concatSet);
        }
    }

  • 0
    F

    public class GeneralizedAbbreviation {

    public static void main(String[] args) {
    	String s = "word";
    	GeneralizedAbbreviation ga = new GeneralizedAbbreviation();
    	ga.process(s);
    }
    /**
     * 
     * @param s:  word
     * @return  word, 1ord, w1rd, wo1d, wor1, 2rd, w2d, wo2, 1o1d, 1or1, w1r1, 1o2, 2r1, 3d, w3, 4
     */
    public void process(String s){
    	int length = s.length();
    	double pool = Math.pow(2, length)-1;
    	for(Integer i=0x0;i<=(byte)pool;i++){
    		StringBuffer finalString = new StringBuffer();
    		String s1 = i.toBinaryString(i);
    		String s2 = s.substring(0,length-s1.length());
    
    		finalString.append(s2);
    		
    		int count=0;
    		for(int j=0;j<s1.length();j++){
    			if( s1.charAt(j)=='0' ){
    					if(count!=0){
    						 finalString.append(count);
    						 count=0;
    					}
    				 finalString.append(s.charAt(length-s1.length()+j));
    			}else{//==1
    				 count++;
    			}
    		}
    		if(count!=0){
    			finalString.append(count);
    		}
    		System.out.println(finalString.toString());
    	}
    }
    

    }


  • 0

    //O(2^n) time complexity solution. At each position we can either add a number of a character.

    public ArrayList<String> convert(String str) throws NullPointerException
    {
    	if(str==null)
    	{
    		throw new NullPointerException();
    	}
    	if(str.length()==0)
    	{
    		return Collections.<String>emptyList();
    	}
    	
    	return abbreviate(0,str);
    }
    
    private ArrayList<String> abbreviate(int idx,String s)
    {
    	ArrayList<String> ls;
    	if(idx==s.length()-1)
    	{
    		ls=new ArrayList<String>();
    		ls.add(""+1);
    		ls.add(""+s.charAt(idx));
    		return ls;
    	}
    	ls=abbreviate(idx+1,s);
    	ArrayList<String> newResults=new ArrayList<String>();
    	for(String s:ls)
    	{
    		StringBuilder sb;
    		
    		
    			sb=new StringBuilder(s.length()+1);
    			sb.append(s.charAt(idx));
    			sb.append(s);
    			newResults.add(sb.toString());
    			//add number infront of existing result
               if(s.charAt(0)>='a' && s.charAt(i)<='z')
                 {
    			sb=new StringBuilder(s.length()+1);
    			sb.append(Integer.toString(new Integer(1)));
    			sb.append(s);
    			newResults.add(sb.toString());
    		 //if first char of s is a number
    		 }else
    		{
    			int i=0;
    			while(i<s.length())
    			{
    				if(s.charAt(i)>='a' && s.charAt(i)<='z')
    				{
    					break;
    				}
    				i++;
    			}
    			//get int value of the entire number
    			int v=Integer.parseInt(s.substring(0,i))+1;
    			String suffix=s.substring(i+1);
    			//append character value in front
    			sb=new StringBuilder(s.length());
    			sb.append(Integer.toString(new Integer(v)));
    			sb.append(suffix);
    			newResults.add(sb.toString());	
    		}
    		
    	}
    	ls=newResults;
    	return ls;
    }

  • 0
    S
    public List<String>  f(String word) {
        char[] cs = word.toCharArray();
        int n = cs.length;
        Queue<String> q = new LinkedList<>();
        q.offer("");
        for (int i = 0; i < n; i++) {
            int qs = q.size();
            for (int j = 0; j < qs; j++) {
                String prefix = q.poll();
                // for each prefix we have two options:
                // 1. append the current char cs[i] to the prefix
                q.offer(prefix + String.valueOf(cs[i]));
                // 2. append 1 to the prefix
                q.offer(prefix + "1");
            }
        }
        List<String> result = new ArrayList<>(q.size());
        while (!q.isEmpty()) {
            char[] rs = q.poll().toCharArray();
            // for each word we need to compact the sequences of ones into a number, ex w11d -> w2d, 1111 -> 4
            StringBuilder sb = new StringBuilder();
            int x = 0;
            for (int i = 0; i < rs.length; i++) {
                if (rs[i] == '1')
                    x++;
                else {
                    if (x != 0) {
                        sb.append(x);
                        x = 0;
                    }
                    sb.append(rs[i]);
                }
            }
            if (x != 0)
                sb.append(x);
            result.add(sb.toString());
        }
        return result;
    }

  • 0
    G

    Here's an easy iterative python version.

    def abbrev(someWord):
      n = len(someWord)
      yield someWord
      for nChars in range(1,n+1):
        for start in range(n-nChars+1):
          yield someWord[:start] + str(nChars) + someWord[start+nChars:]
    
    for abb in abbrev('word'):
      print abb
    

  • 0

    Here is my simple Java solution; I believe it's O(N^2). Please lemme know if I'm wrong!

    public static List<String> solution(String s) {
    	List<String> abbs = new LinkedList<String>();
    	abbs.add(s);
    	for (int i = 0; i < s.length(); i++) {
    		for (int j = 1; j <= s.length() - i; j++) {
    			abbs.add(s.substring(0, i) + j + s.substring(j + i));
    		}
    	}
    	return abbs;
    }
    

  • 0
    P

    Javascript

    const abbr = (w) => {
        let f = (w) => {
            if (w == "")
                return [""];
    
            let result = f(w.substr(1));
            return result.map(x => w[0] + x)
                .concat(
                    result.map(x => "1" + x)
                );
    
        };
    
        return f(w).map(x => {
            while (true) {
                let m = /[1][1]+/.exec(x);
                if (!m) return x;
                x = x.replace(m[0], m[0].length);
            }
        });
    };
    
    

  • 0
    P

    @grodrigues3 The code could not generate 1o1d, 1or1, w1r1 cases.


Log in to reply
 

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