Leetcode mais longos parênteses válidos

Question

Link aqui

Incluirei uma solução em Python e C ++ e você pode revisar uma. Estou mais interessado em revisar o código C ++, algo que comecei a aprender recentemente; aqueles que não conhecem C ++ podem revisar o código Python. Ambas as soluções compartilham uma lógica semelhante, portanto, a revisão se aplicará a qualquer uma delas.

---

Declaração do problema

Dada uma string contendo apenas os caracteres '(' e ')', encontre o comprimento da substring de parênteses válida mais longa (bem formada).

Exemplo 1:

Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Exemplo 2:

Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

Exemplo 3:

Input: s = ""
Output: 0

Exemplo 4:

Input: s = "(()()()"
Output: 6

Exemplo 5:

Input: s = "((())((((())))"
Output: 8

Ambas as soluções são Oⁿ e passam em todos os casos de teste, incluindo o limite de tempo, no entanto, estão demorando mais do que eu esperava, especialmente a versão c ++, embora ambas compartilhem a mesma lógica. Preciso melhorar o tempo como prioridade.

longest_parentheses.py

def check_longest(s):
    opened = []
    closed = []
    cum_distance = 0
    max_distance = 0
    for i, ss in enumerate(s):
        if ss == ')':
            if opened:
                closed.append((opened.pop(), i))
        if ss == '(':
            opened.append(i)
    closed = set(sum(closed, ()))
    for j in range(len(s)):
        if j in closed:
            cum_distance += 1
        else:
            cum_distance = 0
        max_distance = max(max_distance, cum_distance)
    return max_distance


if __name__ == '__main__':
    print(check_longest(')((()()()()'))

Estatísticas:

Runtime: 272 ms, faster than 5.14% of Python3 online submissions for Longest Valid Parentheses.
Memory Usage: 15.5 MB, less than 6.57% of Python3 online submissions for Longest Valid Parentheses.

longest_parentheses.h

#ifndef LEETCODE_LONGEST_PARENTHESES_H
#define LEETCODE_LONGEST_PARENTHESES_H

#include <string_view>

int calculate_distance(size_t p_size, const std::vector<size_t> &closed);
int get_longest(const std::string_view &s);

#endif //LEETCODE_LONGEST_PARENTHESES_H

longest_parentheses.cpp

#include "longest_parentheses.h"
#include <vector>
#include <iostream>


int calculate_distance(size_t p_size, const std::vector<size_t> &closed) {
    int cum_distance = 0;
    int max_distance = 0;
    for (size_t i = 0; i < p_size; ++i) {
        if (std::find(closed.begin(), closed.end(), i) != closed.end()) {
            cum_distance++;
        } else {
            cum_distance = 0;
        }
        max_distance = std::max(max_distance, cum_distance);
    }
    return max_distance;
}


int get_longest(const std::string_view &s) {
    std::vector<size_t> opened, closed;
    for (size_t i = 0; i < s.size(); ++i) {
        auto ss = s[i];
        if (ss == ')') {
            if (!opened.empty()) {
                closed.push_back({opened.back()});
                closed.push_back(i);
                opened.pop_back();
            }
        }
        if (ss == '(') {
            opened.push_back(i);
        }
    }
    return calculate_distance(s.size(), closed);
}


int main() {
    std::cout << get_longest(")()())");
}

Estatísticas:

Runtime: 1276 ms, faster than 5.09% of C++ online submissions for Longest Valid Parentheses.
Memory Usage: 9.3 MB, less than 5.04% of C++ online submissions for Longest Valid Parentheses.

Answer 1

Aqui estão algumas coisas que podem ajudá-lo a melhorar seu programa.

Versão C ++

Use todos os #includes necessários

O tipo std::vector<size_t>é usado na definição de calculate_distance()no arquivo de cabeçalho, mas #include <vector>está faltando na lista de inclusões lá. Além disso, std::max()é usado, mas #include <algorithm>está faltando no .cpparquivo.

Minimize a interface

O .harquivo é uma declaração da interface do seu software. A .cppé a implementação dessa interface. É uma boa prática de design minimizar a interface apenas para o que é necessário para programas externos. Por esse motivo, eu removeria a calculate_distance()função do cabeçalho.

Faça funções locais static

Com a interface menor, conforme defendido acima, a calculate_distancefunção se torna um detalhe de implementação usado apenas dentro do .cpparquivo. Por esse motivo, deve ser feito de staticforma que o compilador saiba que é seguro embutir a função.

Use um em switchvez de uma série de ifafirmações

O código atualmente contém isto:

for (size_t i = 0; i < s.size(); ++i) {
    auto ss = s[i];
    if (ss == ')') {
        if (!opened.empty()) {
            closed.push_back({opened.back()});
            closed.push_back(i);
            opened.pop_back();
        }
    }
    if (ss == '(') {
        opened.push_back(i);
    }
}

Seria um pouco mais rápido e mais fácil de ler se fosse escrito assim:

for (size_t i = 0; i < s.size(); ++i) {
    switch(s[i]) {
        case ')':
            if (!opened.empty()) {
                closed.push_back({opened.back()});
                closed.push_back(i);
                opened.pop_back();
            }
            break;
        case '(':
            opened.push_back(i);
            break;
    }
}

Tenha cuidado com os sinais e os não assinados

O que significaria se calculate_distanceretornasse um número negativo? Provavelmente não tem uma interpretação razoável, então, por esse motivo, eu recomendo que ele retorne uma unsignedquantidade em vez de um assinado int.

Escrever funções de teste

Você forneceu algumas entradas de teste na descrição do problema, mas seria bom escrever um script de teste completo para exercer a função. Para esse tipo de coisa, costumo gostar de usar um objeto de teste. Aqui está o que escrevi para este código:

class ParenTest {
public:
    ParenTest(std::string_view input, unsigned longest)
        : input{input}
        , longest{longest}
    {}
    unsigned operator()() const {
        return static_cast<unsigned>(get_longest(input));
    }
    bool test() const {
        return longest == operator()();
    }
    friend std::ostream& operator<<(std::ostream& out, const ParenTest& test) {
        auto calculated = test();
        return out << (calculated == test.longest ? "ok  " : "BAD ") 
            << "\"" << test.input << "\", " << test.longest << ", got " << calculated << "\n";
    }
private:
    std::string_view input;
    unsigned longest;
};

Agora, aqui estão alguns vetores de teste e uma mainrotina:

int main(int argc, char* argv[]) {
    static const std::vector<ParenTest> tests{
        { "(()", 2 },
        { ")()())", 4 },
        { "", 0 },
        { "(()()()", 6 },
        { "((())((((())))", 8 },
        { "(())(())(()))", 12 },
        { "(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(())(()))", 12 },
        { "(())(())(()))(())(())(())(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))", 38 },
        { "(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))", 38 },
        { "(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))"
          "(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))", 38 },
    };
    for (const auto &test : tests) {
        std::cout << test;
    }
}

Para garantir a correção e também fazer um certo tempo, usei meu modelo de cronômetro . A versão final do se mainparece com isto:

#include "longest_parentheses.h"
#include "stopwatch.h"
#include <string_view>
#include <iostream>
#include <vector>

// the ParenTest class goes here

int main(int argc, char* argv[]) {
    static const std::vector<ParenTest> tests{
        { "(()", 2 },
        { ")()())", 4 },
        { "", 0 },
        { "(()()()", 6 },
        { "((())((((())))", 8 },
        { "(())(())(()))", 12 },
        { "(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(())(()))", 12 },
        { "(())(())(()))(())(())(())(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))", 38 },
        { "(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))", 38 },
        { "(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))"
          "(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))", 38 },
    };
    for (const auto &test : tests) {
        std::cout << test;
    }
    if (argc != 2) {
        std::cout << "Usage: " << argv[0] << " num_trials\n";
        return 1;
    }
        
    auto iterations = std::stoul(argv[1]);

    Stopwatch<> timer{};
    bool valid{true}

    for (auto i{iterations}; i; --i) {
        valid &= tests.back().test();
    }

    auto elapsed{timer.stop()};
    if (!valid) {
        std::cout << "The program failed!\n";
        return 2;
    }

    std::cout << iterations << " trials took " << elapsed << " microseconds\n"
        " for an average of " << elapsed/iterations << " microseconds/trial\n";
}

Use um algoritmo melhor

O código existente não é tão ruim, mas não é tão eficiente quanto poderia ser. Na minha máquina com o código mostrado acima e com um milhão de tentativas, leva 5,66 microssegundos por invocação de get_longest()na entrada de teste mais longa, que também é a última do conjunto. Podemos fazer melhor. Aqui está uma rotina alternativa que usa um std::vectorpara rastrear cada início à (medida que ocorrem, mas também faz o cálculo do comprimento do vão à medida que encontra cada fechamento ). Veja como eu fiz:

unsigned get_longest(const std::string_view& in) {
    struct Span {
        std::size_t begin;
        std::size_t end;
        Span(std::size_t begin, std::size_t end)
            : begin{begin}
            , end{end}
        {}
        std::size_t len() const {
            return end - begin + 1;
        }
        bool is_strictly_enclosing(const Span& other) const {
            return other.begin - begin == 1 &&
                      end - other.end == 1;
        }
        bool is_contiguous_with(const Span& other) const {
            return begin - other.end == 1;
        }
    };
    std::vector<std::size_t> parenmatch;
    std::vector<Span> spans;
    std::size_t longest{0};
    for (std::size_t i{0}; i < in.size(); ++i) {
        switch(in[i]) {
            case '(':
                parenmatch.push_back(i);
                break;
            case ')':
                if (!parenmatch.empty()) {
                    Span curr_span{parenmatch.back(), i};
                    parenmatch.pop_back();
                    if (!spans.empty() && curr_span.is_strictly_enclosing(spans.back())) {
                        // destroy the last one
                        spans.pop_back();
                    }
                    if (!spans.empty() && curr_span.is_contiguous_with(spans.back())) {
                        // merge the contiguous spans
                        spans.back().end = curr_span.end;
                    } else {
                        spans.push_back(curr_span);
                    }
                    longest = std::max(longest, spans.back().len());
                } 
                break;
            default:
                parenmatch.clear();
                spans.clear();
        }
    }
    return longest;
}

Provavelmente ainda há espaço para melhorias, mas é assim que funciona. Primeiro, ele controla cada um Spandos parênteses correspondentes e aninhados. Então ()seria corresponder a tal período, como faria (()). O código usa is_strictly_enclosingpara testar isso. Por exemplo, em (()), o par interno é encontrado primeiro e teria um intervalo de {1,2}. O par externo é encontrado por último e tem uma extensão de {0,3}. Se examinarmos a lógica, agora fica claro o que este código está procurando:

bool is_strictly_enclosing(const Span& other) const {
    return other.begin - begin == 1 &&
              end - other.end == 1;
}

Em segundo lugar, há o caso de parênteses correspondentes, mas não aninhados, como ()()ou (())(). Aqui, novamente, usamos uma função-membro de Span:

bool is_contiguous_with(const Span& other) const {
    return begin - other.end == 1;
}

Usando este código, obtemos o seguinte relatório de tempo:

1.000.000 de tentativas levaram 562299 microssegundos para uma média de 0,562299 microssegundos / tentativa

Portanto, esta versão do código é cerca de 10 vezes mais rápida. Observe também que ele lida corretamente com a entrada malformada, como ((*))por exemplo, relatando 0para tal string.

Versão Python

Use elifpara condições mutuamente exclusivas

A verificação para a abertura é (usada, ifmas faria mais sentido usá-la elifaqui porque os dois casos (ou (ou )) são os únicos considerados. Fazer apenas essa alteração diminui cada iteração (usando a mesma string muito longa do código C ++) de 74,167 microssegundos para 72,444 microssegundos.

Não atualize os valores que não foram alterados

O código atualmente possui esta sequência:

for j in range(len(s)):
    if j in closed:
        cum_distance += 1
    else:
        cum_distance = 0
    max_distance = max(max_distance, cum_distance)

Uma rápida olhada no código irá verificar que max_distancesó pode obter um novo valor se a ifdeclaração for verdadeira, então vamos mover a linha para lá. Isso diminui o tempo para 71.680 microssegundos.

Use um algoritmo mais rápido

Mais uma vez, o que funciona na versão C ++ também funciona no Python. Esta é uma versão Python do algoritmo acima:

def get_longest(s):
    parenmatch = []
    spans = []
    longest = 0
    for i, ss in enumerate(s):
        if ss == '(':
            parenmatch.append(i)
        elif ss == ')':
            if parenmatch:
                curr_span = (parenmatch.pop(), i)
                if spans and spans[-1][0] - curr_span[0] == 1 and curr_span[1] - spans[-1][1] == 1:
                    spans.pop()
                if spans and curr_span[0] - spans[-1][1] == 1:
                    spans[-1] = (spans[-1][0], curr_span[1])
                else:
                    spans.append(curr_span)
                longest = max(longest, spans[-1][1] - spans[-1][0] + 1)
    return longest                        

Desta vez, a diferença não é tão dramática, e o tempo para essa função é de 64,562 microssegundos.