Wednesday, December 2, 2015

Zenefits: Combinations

找出一个string里面长度为n (n小于等于string的长度)的所有组合。
这个比较简单 考虑了一下dupilcate 字母

Code (Java):
import java.io.*;
import java.util.*;

public class Solution {
    public List<String> combination(String s, int k) {
        List<String> result = new ArrayList<>();
        if (s == null || s.length() == 0 || k <= 0) {
            return result;
        }
        
        StringBuffer sb = new StringBuffer();
        combinationHelper(0, s, 0, k, sb, result);
        
        return result;
    }
    
    private void combinationHelper(int start, String s, int num, 
                                   int k, StringBuffer sb, List<String> result) {
        if (num == k) {
            result.add(sb.toString());
            return;
        }
        
        for (int i = start; i < s.length(); i++) {
            sb.append(s.charAt(i));
            combinationHelper(i + 1, s, num + 1, k, sb, result);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
    
    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "abcd";
        List<String> result = solution.combination(s, 2);
        
        for (String i : result) {
            System.out.println(i);
        }
    }
}


No comments:

Post a Comment