[Algorithm Challenge] The shortest distance between characters (including parsing and source code)

821.The shortest distance between characters

https://leetcode-cn.com/problems/shortest-distance-to-a-character/

• 821.The shortest distance between characters
  • Question description
  • Solution 1: Center expansion method
    • Ideas
    • Complexity analysis
    • Code (JS/C++)
  • Solution 2: Exchange space for time
    • Ideas
    • Complexity analysis
    • Code (JS/C++)
  • Solution 3: Greedy
    • Ideas
    • Complexity analysis
    • Code (JS/C++/Python)
  • Solution 4: Window
    • Ideas
    • Complexity analysis
    • Code (JS/C++/Python)

Title description

Given a string S and a character C. Returns an array representing the shortest distance from each character in string S to character C in string S.

Example 1:

Input: S = "loveleetcode", C = 'e'
Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]
illustrate:

The length of string S is in the range [1, 10000].
C is a single character and is guaranteed to be a character in the string S.
All letters in S and C are lowercase.

Source: LeetCode
Link: https://leetcode-cn.com/problems/shortest-distance-to-a-character
The copyright belongs to Lingkou Network. For commercial reprinting, please contact the official authorizer. For non-commercial reprinting, please indicate the source.

Solution 1: Center expansion method

Ideas

This is the most intuitive idea. Each character is processed as follows:

• Starting from the current subscript, search for the target character C in two directions: left and right.
• If it is only found in one direction, the character distance is calculated directly.
• If found in both directions, take the minimum value of the two distances.

Complexity analysis

• time complexity:

  O

  (

  N

  2

  )

  O(N^2)

  O(N2), N is the length of S, two-level loop.

• Space complexity:

  O

  (

  1

  )

  O(1)

  O(1).

Code (JS/C++)

JavaScript Code

/**
 * @param {string} S
 * @param {character} C
 * @return {number[]}
 */
var shortestToChar = function (S, C) {<!-- -->
  // result array res
  var res = Array(S.length).fill(0);

  for (let i = 0; i < S.length; i + + ) {<!-- -->
    // If the current target character is the target character, nothing needs to be done
    if (S[i] === C) continue;

    // Define two pointers l, r to find the target character C in the left and right directions respectively, and take the shortest distance
    let l = i,
      r = i,
      shortest = Infinity;

    while (l >= 0) {<!-- -->
      if (S[l] === C) {<!-- -->
        shortest = Math.min(shortest, i - l);
        break;
      }
      l--;
    }

    while (r < S.length) {<!-- -->
      if (S[r] === C) {<!-- -->
        shortest = Math.min(shortest, r - i);
        break;
      }
      r + + ;
    }

    res[i] = shortest;
  }
  return res;
};

C++Code

class Solution {<!-- -->
public:
    vector<int> shortestToChar(string S, char C) {<!-- -->
        vector<int> res(S.length());

        for (int i = 0; i < S.length(); i + + ) {<!-- -->
            if (S[i] == C) continue;

            int left = i;
            int right = i;
            int dist = 0;

            while (left >= 0 || right <= S.length() - 1) {<!-- -->
                if (S[left] == C) {<!-- -->
                    dist = i - left;
                    break;
                }
                if (S[right] == C) {<!-- -->
                    dist = right - i;
                    break;
                }

                if (left > 0) left--;
                if (right < S.length() - 1) right + + ;
            }

            res[i] = dist;
        }

        return res;
    }
};

Solution 2: Exchange space for time

Ideas

Trading space for time is a very common trade-off in programming (and conversely, trading time for space).

Because the position of the target character C in S is unchanged, we can record all the subscripts of C in an array in advancecIndices.

Then iterate through each character in the string S, find the index closest to the current position in cIndices, and calculate the distance.

Complexity analysis

• time complexity:

  O

  (

  N

  ?

  K

  )

  O(N*K)

  O(N?K), N is the length of S, K is the number of times the character C appears in the string,

  K

  < = N K <= N K<=N.

• Space complexity:

  O

  (

  K

  )

  O(K)

  O(K), K is the number of times the character C appears, which is the space consumed by the auxiliary array that records the occurrence subscript of the character C.

Code (JS/C++)

JavaScript Code

/**
 * @param {string} S
 * @param {character} C
 * @return {number[]}
 */
var shortestToChar = function (S, C) {<!-- -->
  //Record all subscripts where the C character appears in the S string
  var cIndices = [];
  for (let i = 0; i < S.length; i + + ) {<!-- -->
    if (S[i] === C) cIndices.push(i);
  }

  // result array res
  var res = Array(S.length).fill(Infinity);

  for (let i = 0; i < S.length; i + + ) {<!-- -->
    //Target character, distance is 0
    if (S[i] === C) {<!-- -->
      res[i] = 0;
      continue;
    }

    //Non-target characters, find the nearest subscript in the subscript array
    for (const cIndex of cIndices) {<!-- -->
      const dist = Math.abs(cIndex - i);

      // Small pruning
      // Note: Because the subscripts in cIndices are increasing, the following dist will also become larger and larger, which can be excluded.
      if (dist >= res[i]) break;

      res[i] = dist;
    }
  }
  return res;
};

C++Code

class Solution {<!-- -->
public:
    vector<int> shortestToChar(string S, char C) {<!-- -->
        int n = S.length();
        vector<int> c_indices;
        // Initialize a vector of size n with default value n.
        vector<int> res(n, n);

        for (int i = 0; i < n; i + + ) {<!-- -->
            if (S[i] == C) c_indices.push_back(i);
        }

        for (int i = 0; i < n; i + + ) {<!-- -->
            if (S[i] == C) {<!-- -->
                res[i] = 0;
                continue;
            }

            for (int j = 0; j < c_indices.size(); j + + ) {<!-- -->
                int dist = abs(c_indices[j] - i);
                if (dist > res[i]) break;
                res[i] = dist;
            }
        }

        return res;
    }
};

Solution 3: Greedy

Ideas

In fact, for each character, it only cares about the C character closest to it, and it doesn’t care about the others. So you can also use the greedy idea here:

1. First traverse the string S from left to right, and use an array left to record the last C /code> character subscript;
2. Then traverse the string S from right to left, and use an array right to record the last Cright side of each character. /code> character subscript;
3. Then iterate through the two arrays at the same time and calculate the minimum distance.

Optimization 1

If you think about it one more step, you won’t actually need the second array. Because for the C characters on the left and right sides, we only care about the one that is closer, so during the second traversal, we can overwrite the value of the first array depending on the situation:

1. No C character appears to the left of the character
2. i - left > right - i (i is the current character subscript, left is the nearest C subscript to the left of the character, right is the character The nearest C subscript on the right)

If the above two situations occur, you can overwrite it, and finally traverse the array again to calculate the distance.

Optimization 2

If we directly record the distance between C and the current character instead of recording the subscript of C, we can also save the process of calculating the distance in the last traversal.

Complexity analysis

• time complexity:

  O

  (

  N

  )

  O(N)

  O(N), N is the length of S.

• Space complexity:

  O

  (

  1

  )

  O(1)

  O(1).

Code (JS/C++/Python)

JavaScript Code

/**
 * @param {string} S
 * @param {character} C
 * @return {number[]}
 */
var shortestToChar = function (S, C) {<!-- -->
  var res = Array(S.length);

  // First traversal: from left to right
  // Find the last subscript of the C character that appears on the left
  for (let i = 0; i < S.length; i + + ) {<!-- -->
    if (S[i] === C) res[i] = i;
    // If there is no C character on the left, mark it with Infinity
    else res[i] = res[i - 1] === void 0 ? Infinity : res[i - 1];
  }

  //Second traversal: from right to left
  // Find the last subscript of the C character now on the right
  // If the C character does not appear on the left side, or the C character appearing on the right side is closer, update res[i]
  for (let i = S.length - 1; i >= 0; i--) {<!-- -->
    if (res[i] === Infinity || res[i + 1] - i < i - res[i]) res[i] = res[i + 1];
  }

  // Calculate distance
  for (let i = 0; i < res.length; i + + ) {<!-- -->
    res[i] = Math.abs(res[i] - i);
  }
  return res;
};

Calculate distance directly:

JavaScript Code

/**
 * @param {string} S
 * @param {character} C
 * @return {number[]}
 */
var shortestToChar = function (S, C) {<!-- -->
  var res = Array(S.length);

  for (let i = 0; i < S.length; i + + ) {<!-- -->
    if (S[i] === C) res[i] = 0;
    //Record distance: res[i - 1] + 1
    else res[i] = res[i - 1] === void 0 ? Infinity : res[i - 1] + 1;
  }

  for (let i = S.length - 1; i >= 0; i--) {<!-- -->
    //Update distance: res[i + 1] + 1
    if (res[i] === Infinity || res[i + 1] + 1 < res[i]) res[i] = res[i + 1] + 1;
  }

  return res;
};

C++Code

class Solution {<!-- -->
public:
    vector<int> shortestToChar(string S, char C) {<!-- -->
        int n = S.length();
        vector<int> dist(n, n);

        for (int i = 0; i < n; i + + ) {<!-- -->
            if (S[i] == C) dist[i] = 0;
            else if (i > 0) dist[i] = dist[i - 1] + 1;
        }

        for (int i = n - 1; i >= 0; i--) {<!-- -->
            if (dist[i] == n
                || (i < n - 1 & amp; & amp; dist[i + 1] + 1 < dist[i]))
                    dist[i] = dist[i + 1] + 1;
        }

        return dist;
    }
};

Python Code

class Solution(object):
    def shortestToChar(self, s, c):
        """
        :type s: str
        :type c: str
        :rtype: List[int]
        """
        n = len(s)
        res = [0 if s[i] == c else None for i in range(n)]

        for i in range(1, n):
            if res[i] != 0 and res[i - 1] is not None:
                res[i] = res[i - 1] + 1

        for i in range(n - 2, -1, -1):
            if res[i] is None or res[i + 1] + 1 < res[i]:
                res[i] = res[i + 1] + 1
        return res

Solution 4: Window

Ideas

Think of C as a dividing line and divide S into windows. Then traverse each window and calculate the minimum distance between each character and the window boundary.

Complexity analysis

• time complexity:

  O

  (

  N

  )

  O(N)

  O(N), N is the length of S.

• Space complexity:

  O

  (

  1

  )

  O(1)

  O(1).

Code (JS/C++/Python)

JavaScript Code

/**
 * @param {string} S
 * @param {character} C
 * @return {number[]}
 */
var shortestToChar = function (S, C) {<!-- -->
  // The left border of the window. If not, initialize it to Infinity. It can also be initialized to S.length.
  let l = S[0] === C ? 0 : Infinity,
    // Window right border
    r = S.indexOf(C, 1);

  const res = Array(S.length);

  for (let i = 0; i < S.length; i + + ) {<!-- -->
    // Calculate the minimum distance from the character to the left and right borders of the current window
    res[i] = Math.min(Math.abs(i - l), Math.abs(r - i));

    // After traversing the characters of the current window, move the entire window to the right
    if (i === r) {<!-- -->
      l = r;
      r = S.indexOf(C, l + 1);
    }
  }

  return res;
};

C++Code

class Solution {<!-- -->
public:
    vector<int> shortestToChar(string S, char C) {<!-- -->
        int n = S.length();

        int l = S[0] == C ? 0 : n;
        int r = S.find(C, 1);

        vector<int> dist(n);

        for (int i = 0; i < n; i + + ) {<!-- -->
            dist[i] = min(abs(i - l), abs(r - i));
            if (i == r) {<!-- -->
                l = r;
                r = S.find(C, r + 1);
            }
        }

        return dist;
    }
};

Python Code

class Solution(object):
    def shortestToChar(self, s, c):
        """
        :type s: str
        :type c: str
        :rtype: List[int]
        """
        n = len(s)
        res = [0 for _ in range(n)]

        l = 0 if s[0] == c else n
        r = s.find(c, 1)

        for i in range(n):
            res[i] = min(abs(i - l), abs(r - i))
            if i == r:
                l = r
                r = s.find(c, l + 1)
        return res

Summary

The above is all the content of this article. I hope it can be helpful to you and solve the algorithm-the shortest distance problem of characters.

If you like this article, please be sure to like, collect, comment, and forward it, it will be of great help to me. It would also be great to buy me a glass of iced Coke!

It has been completed, please continue to pay attention. See you next time~

Attachments

Download