首页 > 代码库 > Telephone Number
Telephone Number
Problem
Print all valid phone numbers of length n subject to following constraints:
If a number contains a 4, it should start with 4
No two consecutive digits can be same
Three digits (e.g. 7,2,9) will be entirely disallowed, take as input
Solution
Recursive + DFS
1 public static List<List<Integer>> generateNumber(int length, List<Integer> baned) { 2 List<List<Integer>> res = new ArrayList<List<Integer>>(); 3 List<Integer> num = new ArrayList<Integer>(); 4 HashSet<Integer> ban = new HashSet<Integer>(); 5 for(int i=0; i<baned.size(); i++) { 6 ban.add(baned.get(i)); 7 } 8 9 helper(res, num, ban, -1, length, 0);10 11 return res;12 }13 14 public static void helper(List<List<Integer>> res, List<Integer> num, HashSet<Integer> ban, int prev, int length, int pos) {15 if(pos == length) {16 res.add(new ArrayList<Integer>(num));17 return;18 }19 20 for(int i=0; i<=9; i++) {21 if(pos != 0 && i == 4) continue; 22 else if(ban.contains(i)) continue;23 else if(i == prev) continue;24 25 num.add(i);26 helper(res, num, ban, i, length, pos+1);27 num.remove(num.size()-1);28 }29 }
Telephone Number
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。