The Longest Common Subsequence Discussions | Algorithms | HackerRank
We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. The Longest Common Subsequence
  5. Discussions

The Longest Common Subsequence

  • ysaakpr
     + 0 comments

    Please check your test case. This is giving a success output, but one of your test failing. Testcase 3 expecting : 27 76 88 55 94 42 56 74 69 7 94 41 8 71 15 43 3 23 49 84 98 89 24 20 14 88

    But 27 76 88 55 94 42 56 74 69 7 94 41 8 71 15 43 3 23 49 84 73 89 24 20 14 88 is also a valid sub secuence for input 50 46 16 27 89 79 60 76 24 88 55 94 57 42 56 74 24 95 55 33 69 29 14 7 94 41 8 71 12 15 43 3 23 49 84 78 73 63 5 46 98 26 40 76 41 89 24 20 68 14 88 26 27 76 88 0 55 99 94 70 34 42 31 47 56 74 69 46 93 88 89 7 94 41 68 37 8 71 57 15 43 89 43 3 23 35 49 38 84 98 47 89 73 24 20 14 88 75 

    package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "strconv"
    "strings"
)

/*
 * Complete the 'longestCommonSubsequence' function below.
 *
 * The function is expected to return an INTEGER_ARRAY.
 * The function accepts following parameters:
 *  1. INTEGER_ARRAY a
 *  2. INTEGER_ARRAY b
 */
// var store map[string][]int32
// func longestCommonSubsequence(a []int32, b []int32) []int32 {
//     store = make(map[string][]int32,10)
//     save(0,0,[]int32{})
//     return recursion(a,b)
// }

// func save(i,j int, val []int32) {
//     store[fmt.Sprintf("%d,%d", i,j)] = val
// }

// func get(i,j int) ([]int32,bool) {
//     v,ok := store[fmt.Sprintf("%d,%d", i,j)]
//     return v,ok
// }

var store [][][]int32
func initStore (a []int32, b []int32) {
    store = make([][][]int32,len(a)+1,len(a)+1)
    for i:= range store {
        store[i] = make([][]int32,len(b)+1,len(b)+1)
    }
}

func save(i,j int, val []int32) {
    store[i][j] = val
}

func get(i,j int) ([]int32,bool) {
    if store[i][j] == nil {
        return store[i][j],false
    } else {
        return store[i][j], true
    }
}

func largeArray(a,b []int32) []int32 {
    if len(a) > len(b) {
        return a
    }
    return b
}

func longestCommonSubsequence(a []int32, b []int32) []int32 {
    initStore(a,b)
    return recursion(a,b)
}

func recursion(a []int32, b []int32) []int32 {
    m,n := len(a),len(b)
 
    if (m == 0 || n==0) {
        return []int32{}
    }
    if v,ok:=get(m,n); ok {
        return v
    }
    a1 := a[0:m-1]
    b1 := b[0:n-1]
    
    if a[m-1] == b[n-1] {
        v:= append(recursion(a1,b1), a[m-1])
        save(m,n,v)
        return v
    } else {
        v := largeArray(recursion(a,b1),recursion(a1,b))
        save(m,n, v)
        return v
    }
}

func main() {
    reader := bufio.NewReaderSize(os.Stdin, 16 * 1024 * 1024)

    stdout, err := os.Create(os.Getenv("OUTPUT_PATH"))
    checkError(err)

    defer stdout.Close()

    writer := bufio.NewWriterSize(stdout, 16 * 1024 * 1024)

    firstMultipleInput := strings.Split(strings.TrimSpace(readLine(reader)), " ")

    nTemp, err := strconv.ParseInt(firstMultipleInput[0], 10, 64)
    checkError(err)
    n := int32(nTemp)

    mTemp, err := strconv.ParseInt(firstMultipleInput[1], 10, 64)
    checkError(err)
    m := int32(mTemp)

    aTemp := strings.Split(strings.TrimSpace(readLine(reader)), " ")

    var a []int32

    for i := 0; i < int(n); i++ {
        aItemTemp, err := strconv.ParseInt(aTemp[i], 10, 64)
        checkError(err)
        aItem := int32(aItemTemp)
        a = append(a, aItem)
    }

    bTemp := strings.Split(strings.TrimSpace(readLine(reader)), " ")

    var b []int32

    for i := 0; i < int(m); i++ {
        bItemTemp, err := strconv.ParseInt(bTemp[i], 10, 64)
        checkError(err)
        bItem := int32(bItemTemp)
        b = append(b, bItem)
    }

    result := longestCommonSubsequence(a, b)

    for i, resultItem := range result {
        fmt.Fprintf(writer, "%d", resultItem)

        if i != len(result) - 1 {
            fmt.Fprintf(writer, " ")
        }
    }

    fmt.Fprintf(writer, "\n")

    writer.Flush()
}

func readLine(reader *bufio.Reader) string {
    str, _, err := reader.ReadLine()
    if err == io.EOF {
        return ""
    }

    return strings.TrimRight(string(str), "\r\n")
}

func checkError(err error) {
    if err != nil {
        panic(err)
    }
}