logo
down
shadow

Make Longest Possible Word Chain with String Array


Make Longest Possible Word Chain with String Array

Content Index :

Make Longest Possible Word Chain with String Array
Tag : javascript , By : Ravenal
Date : November 29 2020, 12:01 PM

will help you The below recursive function getChains() will build you all the possible chains for your use case and stores them in the allChains variable.
As I mentioned in the comments, this problem feels like a Longest Path Problem. If this is the case you cannot do much better than a brute-force solution. Thus the following solution will become very slow if the words array will grow larger, but for the given words it runs in a couple of seconds.
var words = ["Alabama","Alaska","Arizona","Arkansas","California","Colorado","Connecticut","Delaware","Florida","Georgia","Hawaii","Idaho","Illinois","Indiana","Iowa","Kansas","Kentucky","Louisiana","Maine","Maryland","Massachusetts","Michigan","Minnesota","Mississippi","Missouri","Montana","New Hampshire","New Jersey","New Mexico","New York","North Carolina","North Dakota","Ohio","Oklahoma","Oregon","Pennsylvania","Rhode Island","South Carolina","South Dakota","Tennessee","Texas","Utah","Vermont","Virginia","Washington","West Virginia","Wisconsin","Wyoming"];

var allChains = [];
var usedWords = [];
var currentChain = [];

getChains(currentChain, words, usedWords, allChains)

for(var i = 0; i < allChains.length; i++){
  document.write(allChains[i])
  document.write("<br>")
}

function getChains(currentChain, words, usedWords, allChains){
  var found = false;
  for(var x = 0; x < words.length; x++){
    if((currentChain.length == 0 || currentChain[currentChain.length-1].slice(-1) == words[x].toLowerCase().charAt(0)) && !usedWords.includes(x)){
      currentChain.push(words[x]);
      found = true;
      usedWords.push(x);
      getChains(currentChain, words, usedWords, allChains);
    }
  }
  if(!found){
      allChains.push(currentChain.slice());
  }
  currentChain.pop();
  usedWords.pop();
}

Comments
No Comments Right Now !

Boards Message :
You Must Login Or Sign Up to Add Your Comments .

Share : facebook icon twitter icon

Find the length of longest chain formed using given words in String


Tag : java , By : Justin Bowers
Date : March 29 2020, 07:55 AM
I hope this helps . okk friends here the logic and core part which I had made and my puzzle got solved
import java.util.Map;
import java.util.Stack;

public class CandidateCode 
{ 
public static int chainLength=0;
public static void main(String[] args) {
    String s= "peas,sugar,rice,soup";
    int chainLengthfinal=wordChain(s);
    System.out.println("final length:"+chainLengthfinal);
}
public static int wordChain(String input1)
{
    List<String> stringList = new ArrayList<String>();
    stringList= Arrays.asList(input1.split(","));
    boolean ischain = new CandidateCode().hasChain(stringList);
    if (ischain) {
     return chainLength;    
    }
    return 0;

}
Map<Character, List<String>> startsWith = new HashMap<Character, List<String>>();
Map<Character, List<String>> endsWith = new HashMap<Character, List<String>>();

private Character getFirstChar(String str) {
    return str.charAt(0);
}

private Character getLastChar(String str) {
    return str.charAt(str.length() - 1);
}

boolean hasChain(List<String> stringList) {
    for (String str : stringList) {
        Character start = getFirstChar(str);
        Character end = getLastChar(str);
        List<String> startsWithList;
        List<String> endsWithList;

        if (startsWith.containsKey(start)) {
            startsWithList = startsWith.get(start);
        } else {
            startsWithList = new ArrayList<String>();
            startsWith.put(start, startsWithList);
        }

        if (endsWith.containsKey(end)) {
            endsWithList = endsWith.get(end);
        } else {
            endsWithList = new ArrayList<String>();
            endsWith.put(end, endsWithList);
        }
        startsWithList.add(str);
        endsWithList.add(str);
    }

    Stack<String> stringStack = new Stack<String>();
    for (String str : stringList) {
        if (hasChain(stringList.size(), str, stringStack)) {
            System.out.println(stringStack);
            System.out.println("size "+stringStack.size());
            chainLength= stringStack.size();
            return true;
        }
    }

    return false;
}

private boolean hasChain(int size, String startString, Stack<String> stringStack) {
    if (size == stringStack.size()) return true;
    Character last = getLastChar(startString);
    if (startsWith.containsKey(last)) {
        List<String> stringList = startsWith.get(last);
        for (int i = 0; i < stringList.size(); i++) {
            String candidate = stringList.remove(i--);
            stringStack.push(candidate);
            if (hasChain(size, candidate, stringStack)) {
                return true;
            }
            stringStack.pop();
            stringList.add(++i, candidate);
        }
    }

    return false;
 }
}

How to find the longest consecutive chain of numbers in an array


Tag : python , By : Topher Cyll
Date : March 29 2020, 07:55 AM
With these it helps Group the items into subsequences using itertools.groupby based on constant differences from an increasing count (provided by an itertools.count object), and then take the longest subsequence using the built-in max on key parameter len:
from itertools import groupby, count

lst = [0, 1, 3, 5, 7, 8, 9, 10, 12, 13]
c = count()
val = max((list(g) for _, g in groupby(lst, lambda x: x-next(c))), key=len)
print(val)
# [7, 8, 9, 10]

Longest word chain from a list of words


Tag : python , By : potix2
Date : March 29 2020, 07:55 AM
may help you . You can use recursion to explore every "branch" that emerges when every possible letter containing the proper initial character is added to a running list:
words = ['giraffe', 'elephant', 'ant', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse']
def get_results(_start, _current, _seen):
  if all(c in _seen for c in words if c[0] == _start[-1]):
    yield _current
  else:
      for i in words:
        if i[0] == _start[-1]:
          yield from get_results(i, _current+[i], _seen+[i])


new_d = [list(get_results(i, [i], []))[0] for i in words]
final_d = max([i for i in new_d if len(i) == len(set(i))], key=len)
['hedgehog', 'giraffe', 'elephant', 'tiger', 'racoon']
words = ['giraffe', 'elephant', 'ant', 'ning', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse',]
new_d = [list(get_results(i, [i], []))[0] for i in words]
final_d = max([i for i in new_d if len(i) == len(set(i))], key=len)
['ant', 'tiger', 'racoon', 'ning', 'giraffe', 'elephant']

ClickHouse array - find a longest chain of repeating number in array


Tag : arrays , By : Lathentar
Date : March 29 2020, 07:55 AM
hope this fix your issue In Clickhouse I have a column with array of Int16 elements. I'm looking for a way to find a longest chain of repeating number 1. For example, in array [0,1,1,1,5,1,1,1,1,1,2] longest chain of repeating 1 is 5 elements. Is there any way do do it with existing functions ? , Try this query:
SELECT
    /* The source number. */
    data.1 AS number,
    /* The source array. */
    data.2 AS array,
    /* Number the values ​​in each chain. */
    arrayCumSumNonNegative((x, index) -> x = number ? 1 : -index, array, arrayEnumerate(array)) AS partiallySumArray,
    arrayReduce('max', partiallySumArray) AS result
FROM
(
    /* test data set */
    SELECT arrayJoin([
      /**/
      (1, []), 
      (1, [0, 2, 2, 2, 5]), 
      (1, [0, 1, 1, 1, 5, 1, 1, 1, 1, 1,2]), 
      (1, [1, 1, 1, 2, 3, 4, 5, 1, 1]), 
      (1, [-5, 100, 1, 1, 0, 1, 1, 1]),
      (1, [1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0]),
      /**/
      (5, []), 
      (5, [0, 2, 2, 2, 55]),       
      (5, [5, 5, 10, 300, 5, 77, 5])
      ]) AS data
)
FORMAT Vertical

/* Result:

Row 1:
──────
number:            1
array:             []
partiallySumArray: []
result:            0

Row 2:
──────
number:            1
array:             [0,2,2,2,5]
partiallySumArray: [0,0,0,0,0]
result:            0

Row 3:
──────
number:            1
array:             [0,1,1,1,5,1,1,1,1,1,2]
partiallySumArray: [0,1,2,3,0,1,2,3,4,5,0]
result:            5

Row 4:
──────
number:            1
array:             [1,1,1,2,3,4,5,1,1]
partiallySumArray: [1,2,3,0,0,0,0,1,2]
result:            3

Row 5:
──────
number:            1
array:             [-5,100,1,1,0,1,1,1]
partiallySumArray: [0,0,1,2,0,1,2,3]
result:            3

Row 6:
──────
number:            1
array:             [1,1,0,1,1,1,1,1,1,0,0]
partiallySumArray: [1,2,0,1,2,3,4,5,6,0,0]
result:            6

Row 7:
──────
number:            5
array:             []
partiallySumArray: []
result:            0

Row 8:
──────
number:            5
array:             [0,2,2,2,55]
partiallySumArray: [0,0,0,0,0]
result:            0

Row 9:
───────
number:            5
array:             [5,5,10,300,5,77,5]
partiallySumArray: [1,2,0,0,1,0,1]
result:            2
*/

Find the longest word/string in an array


Tag : javascript , By : Vodkat
Date : March 29 2020, 07:55 AM
Related Posts Related QUESTIONS :
  • Node.js xml2js http.request tag matching
  • applying texture to custom plane geometry in Threejs
  • How do I pass an Event as a function parameter in HTML written inside JavaScript variable?
  • Interface of object parameter with default value and default property
  • Does using try / catch rather than `.catch` observable operator with XHR requests reduce performance?
  • In IE11 background colors not working on printing
  • TypeScript interface signature "(): string"
  • Is synchronous XMLHttpRequest supported in Internet Explorer 10 and 11?
  • Axios function not returning any values with js
  • How to use firestore TIMESTAMP to create time-stamp in JavaScript
  • Instantiate subclass without constructing
  • Outputing a created object in javascript to a server side JSON file
  • Transition the numeric labels in a bar chart
  • createBottomTabNavigator: hide just one tab from the tabBar
  • iife vs simple statement behavior with document.title
  • showDialogPopup Refresh Page after Click
  • Child component does not set the initial value passed from the parent: ReactJS
  • Nodejs javascript added to button not responding
  • Trying to define a promise.all
  • Python GEE to extract featurecollection timeseries from Landsat imageries
  • How to write negative binary number?
  • Unable to set property of individual object
  • Why Named Function Expression itself cannot assign Name to another Value?
  • How to reset scroll position on single page pagination
  • How to scroll to bottom of page, when a new message is sent - Socket.io
  • How to reconstruct audio blob from a base64 encoded String?
  • How to calculate numbers within an array of objects
  • Using JavaScript to change CSS properties of SVG circles for all circles that was not clicked
  • Is there value in propTypeing repeat required properties at every level of nested components?
  • Call function if variable does not exist in a filter
  • localStorage value doesn't get updated automatically
  • React not updating state with setState correctly inside promises
  • Direct native JavaScript or jQuery method to get containing block of an element
  • Dynamic JSON object to Html Table
  • How to send Id and file to same controller?
  • How to Make a jQuery Table Cell(td) clickable to Run a Function?
  • Prevent the duplicate function onchange event jQuery
  • Reactjs Input Upload doesn't return local URL
  • An unexpected 'StartObject' node was found when reading from the JSON reader. A 'PrimitiveValue' node was expected
  • How to filter a JSON Array, with an eventListener input value at keyup
  • How to separate the different properties of filter in css?
  • Why dont work change event of bootstrap input spinner?
  • How to hide overflow text content in react
  • Is there another way to write line 6
  • Cypress - how to find by text content?
  • How to setstate for the dynamic checkboxes in a loop in react?
  • Is display:none safe?
  • How to create a form to change part of a href url of a button?
  • Put many function inside function in Javascript
  • how to exit from loop after a ajax call
  • Do Angular Reactive Form Validator.min/max check Perform Type Conversions before checking the value?
  • How to Replace Text Within Script Tags Using JQuery
  • add variable to object if not undefined using short-hand
  • How can I effectively curve my items inside a list?
  • Add new record Keyboard Shortcut on Kendo Grid Mvc
  • Time and Date running on page
  • Looping through page links puppeteer doesn't return values from the newly loaded page
  • Problem with Navigator.geoLocation.getCurrentPosition not working
  • Trying to change the id of an element with Javascript
  • Embedded Schema Inserting Blank in Meteor using Collection2
  • shadow
    Privacy Policy - Terms - Contact Us © scrbit.com