当前位置：网站首页>The shortest distance of dynamic programming characters

The shortest distance of dynamic programming characters

2022-04-22 12:53:00 【Frank. Ren】

Give you a string s And a character c , And c yes s Characters that have appeared in .

Returns an array of integers answer , among answer.length == s.length And answer[i] yes s From the subscript i To leave it lately The characters of c Of distance .

Two subscripts i and j Between distance by abs(i - j) , among abs Is an absolute value function .

class Solution {
    public int[] shortestToChar(String s, char c) {
        int len = s.length();
        int[] ret = new int[len];
        Arrays.fill(ret, len);
        for (int i = 0, j = -1; i < len; i++) {
            if (s.charAt(i) == c) {
                j = i;
            }
            if (j != -1) {
                ret[i] = i - j;
            }
        }
        for (int i = len - 1, j = -1; i >= 0; i--) {
            if (s.charAt(i) == c) {
                j = i;
            }
            if (j != -1) {
                ret[i] = Math.min(ret[i], j - i);
            }
        }
        return ret;
    }
}

 

 

版权声明
本文为[Frank. Ren]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/04/202204221251148296.html

边栏推荐

猜你喜欢

随机推荐