给一个pattern和一个string, 问string是否满足pattern. 这次string里面的word没有空格. 所以我们要backtracking所有的可能的string的组合, 对于每个组合, 我们都需要添加到hashmap中, 这里, 我们在遍历pattern和string时, 要同时记录pattern中每个char对应在pattern的位置和当前string中substring对应的pattern的位置. 通过string和pattern在pattern中的位置i来判断是否相同. 为了区分pattern和string, 我们可以同两个hashmap, 也可以用一个, 用一个的时候, 注意要用 HashMap<Object,Integer> map 因为pattern存的是<char,integer>,而string存的是<string,integer>, 所以用一个hashmap可以通过比较类型来区别key是pattern或string. 其实是这题和word pattern都是isomorphic问题. public boolean wordPatternMatch(String pattern, String str) { HashMap map = new HashMap(); return dfs(pattern, 0, str, 0, map); } private boolean dfs(String pattern, int i, String str, int j, HashMap map){ if(i == pattern.length() […]

给一个pattern和一个string, 问这个string是否满足这个pattern. 用一个hashmap, 存pattern的每个char和string每个单词, 然后遍历pattern. 如果出现以下两种情况, 则不满足: map中包含这个pattern,但是对应的value不是string的word, 说明已存在其他的mapping. map中不包含这个pattern,但是里面已经有了这个string的word,说明已存在其他的mapping. 其他的返回true. public boolean wordPattern(String pattern, String str) { if (pattern == null || str == null) { return false; } char[] patterns = pattern.toCharArray(); String[] strs = str.split(” “); if (patterns.length != strs.length) { return false; } Map<Character, String> map = new HashMap<Character, String>(); for […]

给一个string s, 包含’+’和’-‘, 给一个操作, 可以翻转++变成–, 两个人比赛, 看谁先不能翻转, 对方就赢了. 问你哪种setting可以保证先手的人必胜. 这个backtracking很好想, 就是假设call这个function的人是先手, 然后尝试所有的翻转, 如果不能翻就说明先手的人不能保证必胜. public boolean canWin(String s) { for (int i = 0; i < s.length() – 1; ++i) if (s.charAt(i) == ‘+’ && s.charAt(i + 1) == ‘+’ && !canWin(s.substring(0, i) + “–” + s.substring(i + 2))) return true; return false; } 这个是O(2^n)的解法 然后看到评论中有一个dp解法. […]

给一个string s, 问翻转其中两个连续的+号, 能有几种翻法? public List<String> generatePossibleNextMoves(String s) { List<String> res = new ArrayList<String>(); for (int i = 0; i < s.length() – 1; i++) { if (s.charAt(i) == ‘+’ && s.charAt(i + 1) == ‘+’) { res.add(s.substring(0, i) + “–” + s.substring(i + 2, s.length())); } } return res; }