Solusi Leetcode - Valid Number

String angka bisa berisi sign, titik desimal, dan exponent. Posisi ketiganya menentukan apakah string itu valid. Saya mencoba empat pendekatan sebelum akhirnya memilih yang paling jelas.

Soalnya meminta kita memvalidasi string seperti "2", "-0.1", "4.", "2e10" sambil menolak "abc", "1e", "99e2.5", dan format lain yang nggak valid. Keempat pendekatan itu memperlihatkan tradeoff yang berbeda antara keringkasan, state yang eksplisit, dan maintainability.

Format angka yang valid

Grammar input-nya punya dua kelompok contoh:

Yang ini harus lolos:

• Integer biasa: "2", "0089"
• Angka dengan sign: "-0.1", "+3.14"
• Angka desimal: "4.", "-.9", ".1"
• Angka dengan exponent: "2e10", "-90E3", "3e+7"

Yang ini nggak boleh lolos:

• "abc": nggak ada digit sama sekali
• "1e": exponent tanpa digit
• "99e2.5": nggak boleh ada desimal setelah exponent
• "--6": banyak sign sekaligus nggak masuk akal
• "1a", "e3", "95a54e53": campuran karakter yang valid dan nggak valid

Percobaan pertama: Regex

Saya mulai dengan regular expression karena format ini kelihatan seperti masalah pattern matching.

Versi pertamanya seperti ini:

function isValidNumberNaive(s) {
  const pattern = /^\s*[+-]?(\d+\.?\d*|\.\d+)([eE][+-]?\d+)?\s*$/;
  return pattern.test(s);
}

Pattern ini cocok dengan contoh-contoh awal. Kalau diurai, pattern-nya seperti ini:

• ^\s*: Lewati whitespace di awal
• [+-]?: Plus atau minus yang opsional
• (\d+\.?\d*|\.\d+): Bagian angka (digit dengan desimal opsional, ATAU desimal dengan digit)
• ([eE][+-]?\d+)?: Bagian exponent yang opsional
• \s*$: Lewati whitespace di akhir

Pattern-nya ringkas, tapi aturannya susah diperiksa. Kalau requirement-nya berubah, saya harus memeriksa ulang setiap quantifier dan alternatifnya. Match yang gagal juga bakal susah didiagnosis.

Edge case baru bakal bikin tradeoff itu makin buruk, karena setiap perubahan menambah cabang baru ke pattern yang udah susah dibaca.

Analisis Performa: Pendekatan Regex

Pattern yang pendek nggak menjamin scan yang linear. V8 menjelaskan bagaimana engine backtracking mereka mencoba alternatif lain setelah match gagal.

Time Complexity: Berpotensi O(n²) karena backtracking

Di pattern ini, \d+ dan \d* sama-sama bisa memakan deretan digit yang sama kalau titik desimal opsionalnya nggak ada. Deretan digit yang panjang lalu diikuti karakter yang nggak valid bisa bikin engine mencoba ulang banyak cara membagi digit-digit itu. Optimasi engine atau algoritma matching yang lain bisa mengubah perilaku ini.

Space Complexity: Tergantung engine

Pattern yang dioper ke .test() ukurannya konstan, tapi itu nggak menentukan working memory dari matcher-nya. Engine-nya mungkin menyimpan state backtracking.

Parser eksplisit di bawah ini bikin scan linear-nya lebih gampang diverifikasi.

Percobaan kedua: Parsing eksplisit

Lalu saya menulis grammar yang sama sebagai langkah-langkah parsing yang eksplisit:

function isValidNumberBetter(s) {
  // Step 1: Skip leading whitespace
  let i = 0;
  while (i < s.length && s[i] === " ") i++;
  if (i >= s.length) return false;

  // Step 2: Check for optional sign
  if (s[i] === "+" || s[i] === "-") i++;

  let hasNumber = false;
  let hasDot = false;

  // Step 3: Parse digits before decimal
  while (i < s.length && /[0-9]/.test(s[i])) {
    hasNumber = true;
    i++;
  }

  // Step 4: Parse optional decimal part
  if (i < s.length && s[i] === ".") {
    hasDot = true;
    i++;
    while (i < s.length && /[0-9]/.test(s[i])) {
      hasNumber = true;
      i++;
    }
  }

  // Step 5: We need at least one digit
  if (!hasNumber) return false;

  // Step 6: Parse optional exponent
  if (i < s.length && (s[i] === "e" || s[i] === "E")) {
    i++;
    if (i < s.length && (s[i] === "+" || s[i] === "-")) i++;

    let exponentHasNumber = false;
    while (i < s.length && /[0-9]/.test(s[i])) {
      exponentHasNumber = true;
      i++;
    }

    if (!exponentHasNumber) return false;
  }

  // Step 7: Skip trailing whitespace
  while (i < s.length && s[i] === " ") i++;

  return i === s.length;
}

Parser-nya pertama melewati spasi dan membaca sign yang opsional. Lalu dia mem-parse angka, bagian desimal, dan exponent. Pengecekan terakhir menolak karakter yang masih tersisa. Contoh-contohnya lolos, tapi menurut saya fase-fase yang terpisah ini susah diikuti sebagai satu aturan validasi.

Analisis Performa: Pendekatan Step by Step

Kompleksitas parser eksplisit ini:

Time Complexity: O(n)

• Saya pakai satu index i yang bergerak dari awal sampai akhir string
• Setiap karakter diperiksa tepat satu kali
• Nggak ada nested loop yang bakal melipatgandakan kerjanya
• Loop while-nya berurutan, bukan nested

Space Complexity: O(1)

• Saya cuma pakai beberapa variabel boolean (hasNumber, hasDot) dan integer (i)
• Ukurannya nggak bertambah seiring ukuran input. Space-nya konstan
• Nggak ada array atau struktur data yang membesar seiring input

Hasilnya tetap O(n) time dan O(1) space, sambil membuat setiap langkah validasi kelihatan. Karena kelihatan, debugging dan perubahan di masa depan jadi lebih gampang.

Percobaan ketiga: State machine

Waktu itu saya lagi baca-baca tentang formal methods, jadi saya memodelkan grammar-nya sebagai state machine. Setiap karakter memindahkan kita ke state baru, dan cuma state tertentu yang boleh jadi akhir dari angka yang valid.

State machine yang dihasilkan:

function isValidNumberOptimized(s) {
  // Define all possible states
  const State = {
    START: 0, // Initial state
    SIGN: 1, // Just read a sign
    INTEGER: 2, // Reading integer digits
    DOT: 3, // Just read a dot
    DECIMAL: 4, // Reading decimal digits
    EXPONENT: 5, // Just read exponent
    EXPONENT_SIGN: 6, // Reading exponent sign
    EXPONENT_NUMBER: 7, // Reading exponent digits
    END: 8, // Valid ending state
  };

  // Define state transitions
  const transitions = {
    [State.START]: {
      digit: State.INTEGER,
      "+": State.SIGN,
      "-": State.SIGN,
      ".": State.DOT,
      " ": State.START,
    },
    [State.SIGN]: {
      digit: State.INTEGER,
      ".": State.DOT,
    },
    [State.INTEGER]: {
      digit: State.INTEGER,
      ".": State.DECIMAL,
      e: State.EXPONENT,
      E: State.EXPONENT,
      " ": State.END,
    },
    [State.DOT]: {
      digit: State.DECIMAL,
    },
    [State.DECIMAL]: {
      digit: State.DECIMAL,
      e: State.EXPONENT,
      E: State.EXPONENT,
      " ": State.END,
    },
    [State.EXPONENT]: {
      digit: State.EXPONENT_NUMBER,
      "+": State.EXPONENT_SIGN,
      "-": State.EXPONENT_SIGN,
    },
    [State.EXPONENT_SIGN]: {
      digit: State.EXPONENT_NUMBER,
    },
    [State.EXPONENT_NUMBER]: {
      digit: State.EXPONENT_NUMBER,
      " ": State.END,
    },
    [State.END]: {
      " ": State.END,
    },
  };

  let currentState = State.START;

  // Process each character
  for (let char of s) {
    let charType = "";

    // Categorize the character
    if (char >= "0" && char <= "9") {
      charType = "digit";
    } else if (char === "+" || char === "-") {
      charType = char;
    } else if (char === ".") {
      charType = ".";
    } else if (char === "e" || char === "E") {
      charType = "e";
    } else if (char === " ") {
      charType = " ";
    } else {
      return false;
    }

    // Check if transition is valid
    if (
      !transitions[currentState] ||
      !Object.prototype.hasOwnProperty.call(transitions[currentState], charType)
    ) {
      return false;
    }

    // Move to next state
    currentState = transitions[currentState][charType];
  }

  // Check if we ended in a valid state
  return [
    State.INTEGER,
    State.DECIMAL,
    State.EXPONENT_NUMBER,
    State.END,
  ].includes(currentState);
}

Tabel ini membuat transisi yang diizinkan jadi eksplisit. Setiap state merepresentasikan apa yang udah muncul sejauh ini, dan setiap transisi menentukan apa yang boleh datang berikutnya.

Mengimplementasikannya lebih susah dari yang saya kira. Tabel transisinya ribet untuk di-maintain, dan kegagalan lebih susah dilokalisasi dibanding di parser eksplisit.

Hasilnya adalah tradeoff yang berguna: model yang rapi secara matematis tetap bisa kurang cocok untuk grammar yang kecil.

Analisis Performa: Pendekatan State Machine

Kompleksitas state machine ini:

Time Complexity: O(n)

• Saya memproses setiap karakter tepat satu kali di for loop utama
• Setiap kategorisasi karakter dan transisi state itu O(1)
• Pengecekan state akhir dengan .includes() itu O(1) karena cuma mengecek array tetap berisi 4 state
• Secara keseluruhan: n karakter × operasi O(1) = O(n)

Space Complexity: O(1)

• Object State dan object transitions ukurannya konstan (9 state, jumlah transisi tetap)
• currentState adalah number
• charType adalah string, tapi panjangnya terbatas (maksimal "EXPONENT_NUMBER", yang konstan)
• Walaupun saya membuat object-object ini sekali, ukurannya nggak bertambah seiring ukuran input

Tradeoff:

• Kelebihan: Transisi yang eksplisit dan himpunan state yang tetap
• Kekurangan: Kode dan indirection yang lebih banyak dari yang dibutuhkan grammar ini, dengan kegagalan yang tersebar di seluruh tabel transisi
• Kapan berguna: Kalau aturan validasinya punya cukup banyak state sampai tabel transisi bikin aturannya lebih jelas

Scan-nya tetap O(n). Perbandingan ini nggak menyertakan benchmark runtime, jadi keputusannya bergantung pada readability dan seberapa banyak state yang dibutuhkan aturannya.

Solusi akhir: Boolean flags

Implementasi akhirnya melacak empat fakta tentang input dengan boolean flags. Cara ini bikin aturannya tetap kelihatan tanpa tabel transisi dari percobaan sebelumnya.

function isValidNumber(s) {
  // Remove leading and trailing whitespace
  s = s.trim();

  // Track what we've seen with simple boolean flags
  let seenDigit = false; // Have we seen any digits?
  let seenDot = false; // Have we seen a decimal point?
  let seenE = false; // Have we seen an exponent?
  let digitAfterE = true; // Do we have digits after the exponent?

  for (let i = 0; i < s.length; i++) {
    const currentChar = s[i];

    if (/[0-9]/.test(currentChar)) {
      // Found a digit
      seenDigit = true;
      if (seenE) {
        // If we're after an exponent, mark that we have digits
        digitAfterE = true;
      }
    } else if (currentChar === "+" || currentChar === "-") {
      // Sign can only appear at start or right after 'e'/'E'
      if (i > 0 && s[i - 1] !== "e" && s[i - 1] !== "E") {
        return false;
      }
    } else if (currentChar === ".") {
      // Can't have multiple dots or dots after exponent
      if (seenDot || seenE) return false;
      seenDot = true;
    } else if (currentChar === "e" || currentChar === "E") {
      // Can't have multiple exponents or exponent without digits
      if (seenE || !seenDigit) return false;
      seenE = true;
      digitAfterE = false; // Reset flag for exponent part
    } else {
      // Any other character is invalid
      return false;
    }
  }

  // Valid if: we saw digits AND (no exponent OR digits after exponent)
  return seenDigit && digitAfterE;
}

Setiap flag mencatat satu kondisi, dan loop-nya cuma jalan satu kali. Saya bisa menambah aturan validasi tanpa harus mengubah tabel transisi. Implementasi ini lolos test suite bersama berisi 32 kasus yang dipakai untuk memverifikasi contoh-contohnya.

Analisis Performa: Pendekatan Boolean Flags (Solusi Akhir)

Kompleksitas implementasinya bisa dilihat langsung dari kodenya:

Time Complexity: O(n)

• Saya mengiterasi setiap karakter tepat satu kali dengan for loop
• Semua operasi di dalam loop itu O(1): perbandingan, assignment, pengecekan boolean
• Operasi .trim() itu O(n), tapi itu tertutupi oleh loop utama yang juga O(n)
• Total: O(n) + O(n) = O(n)

Space Complexity: O(n) di implementasi ini

• State parser-nya pakai 4 variabel boolean dan satu index loop, jadi bagian itu O(1)
• s.trim() bisa mengalokasikan salinan input yang udah dinormalisasi, yang butuh O(n) extra space di worst case
• Trim berbasis index bisa menjaga state parser dan extra space keseluruhannya tetap O(1), tapi itu bukan implementasi yang ditunjukkan di sini

Yang dijamin versi ini:

1. Linear time: Kamu nggak bisa lebih baik dari O(n) karena kamu perlu memeriksa setiap karakter
2. State parser yang terbatas: Flag dan index loop tetap O(1), walaupun trim() bikin implementasi ini butuh O(n) extra space di worst case

Ringkasan Perbandingan Kompleksitas

Perbandingan pendekatan-pendekatannya:

Pendekatan-pendekatan ini berbeda dalam cara merepresentasikan grammar dan mengalokasikan memori. Pendekatan boolean flags punya state parser yang paling jelas, sementara pemanggilan trim() di dalamnya menambah O(n) extra space di worst case.

Tes input valid dan nggak valid

Contoh-contoh ini mencakup bentuk valid dan nggak valid yang utama:

const testCases = [
  { input: "0", expected: true },
  { input: "e", expected: false },
  { input: ".", expected: false },
  { input: " 0 ", expected: true },
  { input: " 0.1 ", expected: true },
  { input: "2e10", expected: true },
  { input: "abc", expected: false },
  { input: "1a", expected: false },
  { input: "1e", expected: false },
  { input: "99e2.5", expected: false },
];

testCases.forEach(({ input, expected }) => {
  const result = isValidNumber(input);
  console.log(
    `"${input}" -> ${result} (expected ${expected}) ${
      result === expected ? "✓" : "✗"
    }`
  );
});

Kasus-kasus contoh ini lolos. Trace di bawah ini menunjukkan alasannya:

Contoh 1: "2e10" (harusnya valid)

• Awal: seenDigit=false, seenDot=false, seenE=false, digitAfterE=true
• '2' → seenDigit = true
• 'e' → seenE = true, digitAfterE = false (di-reset untuk exponent)
• '1' → seenDigit = true, digitAfterE = true (ketemu digit setelah exponent)
• '0' → seenDigit = true, digitAfterE = true
• Akhir: seenDigit=true AND digitAfterE=true → return true ✓

Contoh 2: "1e" (harusnya nggak valid)

• Awal: seenDigit=false, seenDot=false, seenE=false, digitAfterE=true
• '1' → seenDigit = true
• 'e' → seenE = true, digitAfterE = false (di-reset untuk exponent)
• Akhir: seenDigit=true AND digitAfterE=false → return false ✗

Contoh 3: "99e2.5" (harusnya nggak valid)

• Awal: seenDigit=false, seenDot=false, seenE=false, digitAfterE=true
• '9' → seenDigit = true
• '9' → seenDigit = true
• 'e' → seenE = true, digitAfterE = false
• '2' → seenDigit = true, digitAfterE = true
• '.' → langsung return false (nggak boleh ada desimal setelah exponent) ✗

Poin penting

1. Solusi yang jalan belum tentu gampang di-maintain. Regex-nya lolos semua contoh, tapi pendekatan yang eksplisit bikin aturan validasinya lebih gampang diperiksa dan diubah.

2. Struktur formal ada harganya. State machine bisa memperjelas transisi yang kompleks, tapi empat flag udah cukup untuk grammar ini dan butuh mekanisme yang lebih sedikit.

3. State yang gampang dibaca bikin debugging jadi lokal. Setiap flag mendeskripsikan satu invariant, jadi input yang nggak valid bisa dilacak ke aturan yang menolaknya.

4. Big O nggak mendeskripsikan setiap detail implementasi. Parser eksplisit melakukan scan dalam O(n) time. Regex bisa backtracking. Parser akhirnya memakai O(n) extra space kalau trim() mengalokasikan string yang dinormalisasi. State parser-nya sendiri tetap O(1).

Untuk soal ini, parser boolean flags adalah versi yang bakal saya pertahankan. Aturannya kelihatan, lolos semua tes, dan masih ada ruang untuk perubahan tanpa menyembunyikan perilakunya di balik pattern atau tabel transisi.