Topic link

Two-way traversal

The basic concept

Train of thought

Traversal only once can not solve the problem, when traversal from left to right, can only calculate the distance between the current character and the left target character, do not know the right, can not compare the minimum value. So we have to iterate twice, one forward and one backward.

Steps:

  1. Create a result arrayans, forward traversal once, record the position of the target character obtained last timepreMatch, stores the distance between the current character and the last target characteri - preMatch;
  2. Reverse traversal once, obtain the distance from the target character, and the distance calculated last time, take the minimum value;
  3. Return result arrayans.

The illustration

Suppose the string s is: “hellow” and the character C is: “L”.

First loop:

Second loop:

code

function shortestToChar(s: string, c: string) :number[] {
    let ans = [];
    let prevMatch = Number.MIN_SAFE_INTEGER; // Define the minimum value

    // forward traversal
    for (let i = 0; i < s.length; i++) {
        if (s[i] === c) {
            prevMatch = i;  // Record the position of the target character
        }
       // I >= prevMatch; // I >= prevMatch; When prevMatch is MIN_SAFE_INTEGER, the subtraction is a large value
        ans[i] = i - prevMatch;
    }

    prevMatch = Number.MAX_SAFE_INTEGER; // specifies the maximum value
    // Reverse traversal
    for (let i = s.length - 1; i >= 0; i--) {
        if (s[i] === c) {
            prevMatch = i; // Record the position of the target character
        }
        ans[i] = Math.min(prevMatch - i, ans[i]); // Compare with forward traversal, take the smallest position as the last value
    }

    return ans;
};
Copy the code

Optimized version

This can also be optimized to store the last destination string without using the extra variable preMatch, and the assignment logic is a bit different.

The illustration

Suppose the string s is: “hellow” and the character C is: “L”.

code

function shortestToChar(s: string, c: string) :number[] {
    const { length } = s;
    let ans = new Array(length).fill(length - 1); // initialize all values to the maximum distance

    // forward traversal
    ans[0] = s[0] === c ? 0 : ans[0]; // boundary value processing
    for (let i = 1; i < length; i++) { // Start from 1 to prevent overflow of 1ans[i] = s[i] ! == c ? ans[i -1] + 1 : 0; // If it is the target character, the value is 0, otherwise the distance from the previous character is + 1
    }

    // Reverse traversal
    ans[length - 1] = s[length - 1] === c ? 0 : ans[length - 1]; // boundary value processing
    for (let i = length - 2; i >= 0; i--) { // Start with length-2 to prevent overflow of + 1
        // If it is the target character, the value is 0; otherwise, the distance from the previous character is + 1, and the value is compared with the value recorded last time
        ans[i] = Math.min(ans[i], s[i] ! == c ? ans[i +1] + 1 : 0);
    }

    return ans;
};
Copy the code