Hackerrank - Common Child - Pavol Pidanič

Problem Statement
A description of the problem can be found on Hackerrank.

Solution
The implementation according to Longest Common Subsequence Problem.

Ruby solutions is implemented with the same algorithm as Java solution. One hackerrank test with Ruby solution failed on timeout.

I created solution in:

Java
Ruby

All solutions are also available on my GitHub.

Java

import java.util.Scanner;

public class CommonChild
{
    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
        String input1 = scanner.nextLine();
        String input2 = scanner.nextLine();

        int result = lcsOptimized(input1, input2);
        System.out.println(result);
        scanner.close();
    }

    private static int lcsOptimized(String input1, String input2)
    {
        int start = 0;
        int inEnd1 = input1.length() - 1;
        int inEnd2 = input2.length() - 1;

        while (start <= inEnd1 && start <= inEnd2
                && input1.charAt(start) == input2.charAt(start))
        {
            start++;
        }

        while (start <= inEnd1 && start <= inEnd2
                && input1.charAt(inEnd1) == input2.charAt(inEnd2))
        {
            inEnd1--;
            inEnd2--;
        }
        int[][] table = new int[inEnd1 - start + 1][inEnd2 - start + 1];
        for (int i = 0; i < table.length; i++)
        {
            for (int j = 0; j < table[i].length; j++)
            {
                table[i][j] = input1.length() - inEnd1 - 1;
            }
        }

        for (int i = start; i < inEnd1; i++)
        {
            for (int j = start; j < inEnd2; j++)
            {
                if(input1.charAt(i) == input2.charAt(j))
                {
                    table[i + 1][j + 1] = table[i][j] + 1;
                }
                else
                {
                    table[i + 1][j + 1] = table[i + 1][j] > table[i][j + 1] ? table[i + 1][j]
                            : table[i][j + 1];
                }
            }
        }

        return table[inEnd1][inEnd2];
    }
}

import java.util.Scanner;

public class CommonChild

{

public static void main(String[] args)

{

Scanner scanner = new Scanner(System.in);

String input1 = scanner.nextLine();

String input2 = scanner.nextLine();

int result = lcsOptimized(input1, input2);

System.out.println(result);

scanner.close();

}

private static int lcsOptimized(String input1, String input2)

{

int start = 0;

int inEnd1 = input1.length() - 1;

int inEnd2 = input2.length() - 1;

while (start <= inEnd1 && start <= inEnd2

&& input1.charAt(start) == input2.charAt(start))

{

start++;

}

while (start <= inEnd1 && start <= inEnd2

&& input1.charAt(inEnd1) == input2.charAt(inEnd2))

{

inEnd1--;

inEnd2--;

}

int[][] table = new int[inEnd1 - start + 1][inEnd2 - start + 1];

for (int i = 0; i < table.length; i++)

{

for (int j = 0; j < table[i].length; j++)

{

table[i][j] = input1.length() - inEnd1 - 1;

}

for (int i = start; i < inEnd1; i++)

{

for (int j = start; j < inEnd2; j++)

{

if(input1.charAt(i) == input2.charAt(j))

{

table[i + 1][j + 1] = table[i][j] + 1;

}

else

{

table[i + 1][j + 1] = table[i + 1][j] > table[i][j + 1] ? table[i + 1][j]

: table[i][j + 1];

}

return table[inEnd1][inEnd2];

}

Ruby

def lcs_length_optimized(input1, input2)
  start = 0
  m_end = input1.length - 1
  n_end = input2.length - 1
  while start <= m_end && start <= n_end && input1[start] == input2[start]
    start += 1
  end
  while start <= m_end && start <= n_end && input1[m_end] == input2[n_end]
    m_end -= 1
    n_end -= 1
  end
   
  table = Array.new(m_end - start + 1) { Array.new(n_end - start + 1,  (start - 0) + (input1.length - m_end - 1)) }
  
  for i in start...m_end do
    for j in start...n_end do
      if input1[i] == input2[j]
        table[i + 1][j + 1] = table[i][j] + 1
      else
        table[i + 1][j + 1] = [table[i + 1][j], table[i][j + 1]].max
      end
    end
  end
  return table[m_end][n_end]
end
       
def lcs_length(input1, input2)
  table = Array.new(input1.length + 1) { Array.new(input2.length + 1,  0) }
  
  input1.length.times do |i|
    input2.length.times do |j|
      if input1[i] == input2[j]
        table[i + 1][j + 1] = table[i][j] + 1
      else
        table[i + 1][j + 1] = [table[i + 1][j], table[i][j + 1]].max
      end
    end
  end
  return table[input1.length][input2.length]
end
    
input1 = gets.chomp
input2 = gets.chomp

puts lcs_length_optimized(input1, input2)

def lcs_length_optimized(input1, input2)

start = 0

m_end = input1.length - 1

n_end = input2.length - 1

while start <= m_end && start <= n_end && input1[start] == input2[start]

start += 1

end

while start <= m_end && start <= n_end && input1[m_end] == input2[n_end]

m_end -= 1

n_end -= 1

end

table = Array.new(m_end - start + 1) { Array.new(n_end - start + 1, (start - 0) + (input1.length - m_end - 1)) }

for i in start...m_end do

for j in start...n_end do

if input1[i] == input2[j]

table[i + 1][j + 1] = table[i][j] + 1

else

table[i + 1][j + 1] = [table[i + 1][j], table[i][j + 1]].max

end

return table[m_end][n_end]

end

def lcs_length(input1, input2)

table = Array.new(input1.length + 1) { Array.new(input2.length + 1, 0) }

input1.length.times do |i|

input2.length.times do |j|

if input1[i] == input2[j]

table[i + 1][j + 1] = table[i][j] + 1

else

table[i + 1][j + 1] = [table[i + 1][j], table[i][j + 1]].max

end

return table[input1.length][input2.length]

end

input1 = gets.chomp

input2 = gets.chomp

puts lcs_length_optimized(input1, input2)

Pavol Pidanič

I can count to 1023 with 10 fingers

Hackerrank – Common Child