If I have a road as a string S, and each character in S is:

 "<" -> car going to the left 
 ">" -> car going to the right 
 "." -> speed camera

How can I count the total number of times a car pass by a speed camera? Considering that a car going to the right only passes cameras to its right, and cars going to the left only passes cameras to its left.

The test asks me to write a function: function solution(S); that, given a string S of length N, returns the total number of times that cars pass by a camera. Example:

Given S = ".>..." , the function should return 3.
Given S = ".>.<.>" , the function should return 4.
Given S = ">>>.<<<" , the function should return 6.

I was trying to solve this in Javascript using 2 pointers, but got stuck and ran out of time. Any advice? What would be a good method to resolve this in Javascript?

Thank you.

CodePudding user response：

Use nested loops. The main loop looks for < and > characters. When it sees one of these, it does a second loop counting the number of . characters before or after it, adding this to the total.

function solution(s) {
  let count = 0;
  for (let i = 0; i < s.length; i  ) {
    if (s[i] == '<') {
      for (let j = 0; j < i; j  ) {
        if (s[j] == '.') {
          count  ;
        }
      }
    } else if (s[i] == '>') {
      for (let j = i   1; j < s.length; j  ) {
        if (s[j] == '.') {
          count  ;
        }
      }
    }
  }
  return count;
}

console.log(solution(".>..."));
console.log(solution(".>.<.>"));
console.log(solution(">>>.<<<"));

This is the simple solution, not very efficient (it's O(n^2)). So if you're trying to do this for a code challenge site, it might get a time limit exceeded failure.

CodePudding user response：

You can do a two-pass, one counts the number of times left-going cars passed by cameras while the other counts that for right-going cars. Time complexity is O(n).

function solution(s) {
    let res = 0;
    for (let i = 0, cnt = 0; i < s.length;   i)
        if (s[i] == '.') cnt  ;
        else if (s[i] == '<') res  = cnt;
    
    for (let i = s.length-1, cnt = 0; i >= 0; --i)
        if (s[i] == '.') cnt  ;
        else if (s[i] == '>') res  = cnt;
    return res;
}

console.log(solution(".>..."));
console.log(solution(".>.<.>"));
console.log(solution(">>>.<<<"));