双指针解决字符的最短距离
暴力解法
class Solution { public int[] shortestToChar(String s, char c) { int len = s.length(); ArrayList<Integer> index = new ArrayList<>(); int i = 0; for(i = 0; i < len; i++){ if(s.charAt(i) == c){ index.add(i); } } int[] res = new int[len]; for(i = 0; i < len; i++){ int min = Integer.MAX_VALUE; for(int j = 0; j < index.size(); j++){ min = Math.min(min, Math.abs(i - index.get(j))); } res[i] = min; } return res; } }
双指针降低时间复杂度
不用在索引上依次去遍历目标字符的索引集合找到最近的,而是在第一层循环中更新最近的索引位置。
class Solution { public int[] shortestToChar(String s, char c) { int len = s.length(); int[] res = new int[len]; int l = s.indexOf(c), r = s.indexOf(c, l+1); for(int i = 0; i < s.length(); i++){ res[i] = Math.abs(l - i); if(r != -1){ res[i] = Math.min(res[i], r - i); if(i == r){ res[i] = 0; l = r; r = s.indexOf(c, r + 1); } } } return res; } }